Refactoring my problem-solution to reduce complexity

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 :).

Introduction

Dynamic programming is applicable to this problem, but unfortunately, it's still quadratic (though a significantly lesser quadratic in the usual case).

If you're curious, what tipped me off to DP is the one-directional dependency. In other words, if the voices could go in both directions rather than just forward, dynamic programming would not be possible since a pleasant recurrence relation could not be found.

I've assumed that you've used dynamic programming before and are familiar with it. If you are not, please let me know, and I will try to explain it in more detail.

Problem Consideration

Let's consider the formulation of the problem for a second:

There are n people sitting at a table. Each person i (1 <= i <= n) is sitting at seat x(i), and each person has a voice volume t(i). A volume of t means that the speaker's voice can reach at most t seats (not people) directly. In other words, if a person is at seat 3 with a volume of 5, he can talk to everyone in between his own seat and seat 8 (including seat 8).

A conversation is started by a person p, and it can consist of all people be reached by p, including through intermediary speakers. In other words, if p is at seat 3, and has a volume of 5, a person at seat 9 cannot hear him. If, however, someone is sitting at seat 5 with a volume of 5, p can talk to seat 9 by way of the person in seat 5 (since 5 + 5 = 10; 10 >= 9).

Note: I have used 1-indexing rather than 0-indexing.

Ok, so why am I wording it like this? Notice that there is a recursive relation here. p can talk to anyone whom the people p can talk to directly can talk to. In other words, for each person q, if p can talk to q, then p can also talk to all people to whom q can speak. Like wise, for each person r, if q can speak to them, q can speak to all of the people they can speak to.

In more natural terms, if Mark can talk to Jon and Jon can talk to Steve, then Mark can talk to Steve and everyone to whom Steve can talk.

Informal Solution

Let's formulate this in English and then we'll formulate it mathematically.

In short, the maximum number of people that person i can speak with is the maximum number of people that the people he can directly speak with can speak with.

Imagine that i can speak directly with j, k, and m. There are three options:

1) j can speak with the most people 2) k can speak with the most people 3) m can speak with the most people

Note that picking j must implicitly include k (if you don't see why, ask me).

So, if you pick each option, i can speak with this many people:

1) 1 (since i can speak to himself) + the number of people with whom j can speak 2) 2 + the number of people with whom k can speak. The addition of two instead of is necessary since k's people do not include j, but i can obviously speak with j. 3) 3 + the number of people with whom m can speak. Same logic: j, k, and all of the people with whom m can speak (including m)

Or, in general, for each person, p, to whom i can talk you must consider to how many people p can talk, and add it to the number of people that are between i and p. The maximum of this is the choice you should make.

So, now we should be asking ourselves what the base case is.

The last person can only speak to himself as there is no one past him. This is our base case, and thus our dyamic programming loop will start at the end of all of the people and go back to the beginning.

Formal Solution

Let's formulate this a bit more mathematically now.

For the sake of ease, let's consider a different perspective of the same data: how many people could chair c talk to?

• Let m(c) be the number of people to whom chair c can speak.
• Let v(c) be the number of chairs that c can reach directly.

• Let f(c, d) be the number of occupied chairs between c and d, exclusive.

  If chair c is empty, m(c) = 0 If chair c is the last chair, m(c) = 1 Otherwise,m(c) = 1 + max{f(c, j) + m(c + j)} for 1 <= j <= v(c)`

Let's break down the third case, since it's a bit complicated:

• We have 1 since c can always talk to itself if it's non-empty.
• f(c + 1, j - 1) is the number of occupied chairs between i and j, not including i or j. This is necessary since c can obviously talk to all of the people between it and j (if it can talk to j), but picking chair j does not count all of these people.
• m(c + j) is the recursive (or dynamic programming). It is just the number of people to whom chair c + j can speak. Note that this will always just be a constant-time look up since all m(d) are already known for d > c.
• Ranging from 1 to v(c) is necessary so we consider every chair to which chair c can speak.

That was easy to formulate, but unfortunately, with up to a billion chairs, it's not very feasible. Instead, we need to formulate it in terms of person i rather than chair c. Luckily, this is pretty easy. The last person can only talk to 1 person. For every other person, just use similar logic as to the chairs, but be careful to hop from person to person rather than from chair to chair.

Run time analysis

Unfortunately, now that we've done all of this work, if we stop and think about it, we'll see that this is still quadratic. In the worst case, we must consider every person between the person of question and the last person.

In the non-worst case though, this will handily performance better (asymtotically anyway) than your solution. Your solution keeps going through people until it can no longer reach a person at all. This solution only goes through only people it can reach directly.

Here the first element is denoted as 0-th and last as N-1-th.

Algorithm description

For each element, we can memorize an additional integer: skip[i], initially skip[i] = i + 1. skip[i] points to the next person that has to be considered, when somebody before i is figuring out the total number of people who can hear him. For example, if there are people 0, 1, 2, 3 and it has already been figured out that 1's voice can reach 2, but not 3, then skip[1] = 3 (not 2). So if 0's voice already reaches 1, there is no need to consider whether 2 can also be reached. The algorithm can straight move from 1 to skip[1] = 3-th person.

Also we define K[i] = L[i] + x[i] for each element, the last place where voice of this person can be heard.

The dynamic programming outer loop goes from i = N - 1 to 0. The algorithm also has an inner loop, like this:

for (int j = i; j < N && x[j] <= K[i]; j = skip[j]){
    K[i] = max(K[i], K[j]);
    skip[i] = skip[j];
}

The next time someone's voice would already reach i-th, the voice would also reach everybody before skip[i]-th. Thus next time, we straight go from i to skip[i]. Outer loop ends here.

In the end, the answer for k-th person is simply skip[k] - k.

Proof for O(N) time complexity

Proof for the linear running time:

Observe the sequence

(skip[0], skip[skip[0]], ..., skip[..skip[0]..] = N)

(the sequence will always end with N)

Initially it is (1, 2, ..., N). Each time the inner for loop is executed more than once, one element is skipped from the sequence (skip[0], skip[skip[0]], ..., skip[..skip[0]..] = N) and it will become shorter by exactly one. So the maximal number of inner loop executions during the total execution of the algorithm increases with O(N). Thus total running time complexity is O(N).

Instead of a vector of pairs, use a map. After all, you are guaranteed that no two members will occupy the same seat.

I found your variable names infuriating: a, b, c, r. Surely you could use more descriptive names.

void process(const std::map<int, int> &seatVoice) {
    for (int i = 0; i < seatVoice.size(); i++) {
        std::map<int, int>::const_iterator it = std::next(seatVoice.begin(), i);
        int range = it->first;
        int members = 0;
        do {
            int seat  = it->first;
            int voice = it->second;
            if (seat > range) {
                break;
            }
            members++;
            range = std::max(range, seat + voice);
        } while (++it != seatVoice.end());
        std::cout << members << std::endl;
    }
}