Refactoring my problem-solution to reduce complexity

I need some help refactoring my solution to the problem below:

Problem Statement

An Association of Computer Scientists meets on a weekly basis. There is a certain number of seats in the meeting room and all members know their seats. For example, if there are 10 seats and only 5 members attending, each member will sit on his own seat, and there may be empty seats left between the members, because all have to sit on their ‘reserved’ seats.

If a member, sitting on seat Xi, starts or joins the discussion, exactly Ti people (after him) will take part of the discussion. For every member, we know his seat and his voice. Only those members who are within the reach of the previous member’s voice can hear him and participate in the discussion. For example, if we are given the seat and the voice of a member, and they are 1, 7 (respectively), only people seated on seats within range of 1 to 8 (inclusive) can hear him and participate in the discussion.

Example Data

Input:

N – number of members attending

Xi – seat of member i (for all i=1,2,…N), Li – his voice

Output:

The number of people participating in the discussion after member
i.

Example Input:

5

1 7

2 3

8 7

10 5

100 2

Output:

4

1

2

1

1

And now, here’s my solution:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
        int n;
        cin >> n;
        vector<pair<int, int> > c;
        for (int i=0; i<n; i++) {
                int a, b;
                cin >> a >> b;
                c.push_back(make_pair(a,b));
        }
        for (int i=0; i<n; i++) {
                int a, b, r=1;
                a = c[i].first;
                b = c[i].second;
                for (int j=i+1; j<n; j++) {
                        if (a+b >= c[j].first) {
                                if (c[j].first + c[j].second > a+b) {
                                        a = c[j].first;
                                        b = c[j].second;
                                }
                                r++;
                        }
                }
                cout << r << endl;
        }
    
        return 0;
}

The problem with this solution is in its quadratic O-complexity. Is it possible to reduce it somehow? I’ve been thinking of the divide and conquer approach, but I’m fairly new to the concept, and I have no idea if that’s the right approach for this problem, and how I may implement that.

Answer

I plan to think up a better algorithm later and post an answer on that, but for now, I’d like to offer a critique of your existing code.


Typically using namespace std; should be avoided in favor of either using the std:: qualifier or just importing the identifiers you plan to use at a function level. (E.g. inside of main, doing something like using std::cout;.)


You should verify that your input reading succeeds:

if (!(cin >> n)) { return EXIT_FAILURE; }

(And something similar in your loop.)

On the off chance that something goes wrong, you’d rather bail out with an exit code than do nothing. If you really wanted, you could even put out an error message (though for contest-style problems like these that would be more for your use than the end purpose).


It’s a good habit in C++ to use ++i whenever you can as opposed to i++. For an int or any other built in, it doesn’t particularly matter, but for complex types, ++i can avoid an expensive copy.

The most common manifestation of this is iterators. ++i increments an iterator in place. i++ creates a copy of the iterator, increments the original one and then returns the copy. If you’re not actually capturing the copy, there’s no reason to create one.


Try to give variables more useful names. Imagine coming back to this 6 months from now, or imagine if I hadn’t read the problem statement. I would be left wondering what in the world all these 1 character variable names are. Descriptive variables assist the reader in more quickly comprehending what code is doing.


Rather than pushing back pairs over and over again, I would take advantage of vector‘s values constructor and std::pair‘s default constructor:

std::vector<std::pair<int, int> > attendees(numAttendees);
for (int i = 0; i < numAttendees; ++i) {
    if (!(cin >> attendees[i].first >> attendees[i].second)) {
        return 1;
    }
}

Not only with this have a bit better performance (since it doesn’t have to keep resizing the vector), it is a bit cleaner. (If the pair default ctor actually turns out to be expensive, you could use reserve() to avoid the vector resizing but still allow you to use make_pair to avoid the default construction of each pair.)


Is your input guaranteed to be sorted? If not, you need to either sort or scan over the entire data set rather than starting at i + 1.


This comes down to opinion, but I find space around operators (e.g. i+1 as i + 1) much easier to read. For example for (int i = 0; i < n; ++i) vs for(int i=0; i<n; ++i).


You need to include utility for pair, I believe.


Whenever you have a deep nesting of loops, it’s typically a sign that something should be pulled into a function. For example, I would pull the for(int j = i+1; ...) part of the loop into a function called countInvolvedAttendees (or something hopefully better named — I’m drawing a blank).


std::pair is a double edged sword. It’s very, very convenient for holding any pair, but it’s generality is also it’s downfall. In particular, it basically murders decent naming. When I see a std::pair<int, int>, I have no idea what in the world the two ints are at all. Compare that to a Attendee that has a seatPosition and voiceDistance, and suddenly the meanings are very clear. Unfortunately though, creating a custom struct or class for this seems a bit overkill.

What I’m trying to get across is please be mindful of the problem of std::pair‘s vagueness. In all but the simplest of circumstances, it’s typically better to create something with proper names. Otherwise, it’s too easy to get caught up in first and second and flip them, forgot what one means, and so on.


std::endl is a common case of I don’t think that does what you think it does.

In particular, std::endl is equivalent to os << '\n' << std::flush;.

For lots of outputting, this constant flushing can be shockingly slow. In cases like this, where you’re outputting a giant batch and not responding to human input as it comes, I would use '\n' instead.


Since this is a lot to take in, I might write out a revised version in a bit when I get some more time :).

Attribution
Source : Link , Question Author : Stefan Pavikevik , Answer Author : Corbin

Leave a Comment