# UVA 10474 - “Where is the marble?”

I have been solving the problem from UVA 10474. In this problem, there will be marbles with numbers written on them. For example suppose five marbles with numbers 50 , 43, 43, 43, 2, 90, 44. There will be several query with number and position has to be told in a sorted sequence. For example after sorting these looks like : 2,43,43,43,44,50,90. Now, query for 43 will give output : 43 fond at 2 and query for -3 will output "-3 not found".

Can you please review it and provide me with feedback?

#include <iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>

void printMarbelPositionIfFound()
{
int numMarbles, numQueries, aMarble, case1;
std::vector<int>marbles;

case1 = 0;

while(true)
{
scanf("%d %d", &numMarbles, &numQueries);
if(0 == numMarbles && 0 == numQueries)return;

case1++;

for(int i=0; i<numMarbles; i++)
{
scanf("%d", &aMarble);
marbles.push_back(aMarble);
}

std::sort(marbles.begin(), marbles.end());
std::cout<<"CASE#"<<" "<<case1<<":"<<"\n";
for(int i=0; i<numQueries; i++)
{

scanf("%d", &aMarble);

std::vector<int>::const_iterator itr = std::lower_bound(marbles.begin(), marbles.end(),aMarble);
if(*itr == aMarble)
{
std::cout<<aMarble<<" found at "<<itr - marbles.begin() + 1<<'\n';
}
else
{
}
}

marbles.clear();
}
}

int main()
{
printMarbelPositionIfFound();
return 0;
}

• Since nothing in the problem description forbids it, you could probably get better results using std::find found in the <algorithm> header – tinstaafl Dec 12 '14 at 3:55
• Thanks @tinstaafl . Didn't know about std::find(). I have just checked it. Its time complexity is at most O(n) while std::lower_bound has complexity at most O(lgn). So, I think it will be inefficient compared to std::lower_bound(). – Rumel Dec 12 '14 at 5:06

You are mixing C with C++. I know these contests like speed, but it is usually unnecessary.

1. Prefer streams over scanf.

This means you can change this code:

    scanf("%d %d", &numMarbles, &numQueries);


Into this:

    std::cin >> numMarbles >> numQueries ;


2. Use the C++11 auto keyword when possible.

You have a C++11 tag, so I assume you have C++11 available.
You can change this:

std::vector<int>::const_iterator itr = std::lower_bound(marbles.begin(), marbles.end(),aMarble);


To this:

auto itr = std::lower_bound(marbles.begin(), marbles.end(),aMarble);


3. Make sure the iterator does not point past the end when you dereference it.

In this line: if(*itr == aMarble), you dereference the iterator. If aMarble is not in marbles, then std::lower_bound() will return marbles.end(). It is undefined behavior to dereference marbles.end(). Always check for this condition.

So change this line:

if(*itr == aMarble)


To this:

if (iter != marbles.end () && *itr == aMarble)


4. Prefer pre-increment over post-increment.

You have:

case1++;


In the case an int, it doesn't really matter. Your compiler will optimize this correctly. But if you had a complicated object, then you would be creating an unnecessary copy here. So:

++case1;


Would be a better habit to get into.

5. Encapsulate input and output with an Object.

You could create an object that represents a single unit of input. Something like this:

struct Input
{
int nMarbles ;
int nQueries ;
static int caseNumber ;

std::vector <int> marbles ;
std::vector <int> queries ;

Input () ;
void Clear () ;

friend auto operator>> (std::istream &is, Input &input) -> std::istream& ;
friend auto operator<< (std::ostream &os, const Input &input) -> std::ostream& ;
};


Then you could implement the member and friend functions like this:

int Input::caseNumber = 0 ;

Input::Input () : nMarbles (), nQueries ()
{
}

void Input::Clear ()
{
nMarbles = 0 ;
nQueries = 0 ;
marbles.clear () ;
queries.clear () ;
}

auto operator>> (std::istream& is, Input &input) -> std::istream&
{
++Input::caseNumber ;

is >> input.nMarbles >> input.nQueries ;

if (input.nMarbles == 0 && input.nQueries == 0) {
is.setstate (std::ios::failbit) ;
return is ;
}

auto begin = std::istream_iterator <int> (is) ;
std::copy_n (begin, input.nMarbles, std::back_inserter (input.marbles)) ;

begin = std::istream_iterator <int> (is) ;
std::copy_n (begin, input.nQueries, std::back_inserter (input.queries)) ;

return is ;
}

auto operator<< (std::ostream &os, Input &input) -> std::ostream&
{
os << "CASE# " << Input::caseNumber << ":" "\n" ;

auto &marbles = input.marbles ;

std::sort (std::begin (marbles), std::end (marbles)) ;

for (int query : input.queries) {
auto iter = std::lower_bound (std::begin (marbles), std::end (marbles), query) ;

if (iter != std::end (marbles) && *iter == query) {
os << query << " found at " << (std::distance (std::begin (marbles), iter) + 1) << "\n" ;
}

else {
}
}

return os ;
}


Then your driver would look like this:

int main ()
{
Input input ;

while (std::cin >> input) {
std::cout << input ;
input.Clear () ;
}

return 0 ;
}


With the above code, I got an accepted answer with a runtime of 0.212 units on your website. So streams are more than fast enough for this particular challenge.