4
\$\begingroup\$

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
            {
                std::cout<<aMarble<<" not found"<<'\n';
            }
        }

        marbles.clear();
    }
}

int main()
{
    printMarbelPositionIfFound();
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Since nothing in the problem description forbids it, you could probably get better results using std::find found in the <algorithm> header \$\endgroup\$ – tinstaafl Dec 12 '14 at 3:55
  • \$\begingroup\$ 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(). \$\endgroup\$ – Rumel Dec 12 '14 at 5:06
4
\$\begingroup\$

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 {
            os << query << " not found" "\n" ;
        }
    }

    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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.