# 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.

-
Do you know the maximum number of inputs and do you have a time limit? I'm curious what kind of runtime is likely going to be required. I'm fairly certain that there is a sub-quadratic algorithm, but everything I can think of is relatively unpleasant to actually implement compared to the naive algorithm. My first thought was a tweaked heap, but the more I think about it, I think this is solvable with dynamic programming. –  Corbin Mar 21 at 19:37
I've been thinking about a dynamic programming solution too... The naive algorithm is all well, if used for small inputs, but that's not very satisfying. –  Pilgrim To Programming Mar 21 at 19:46
Oh yeah, 1 <= N <= 100 000 and 1 <= Xi,Li <= 1 000 000 000, where N is the number of attendees, Xi the seat of every member i and Li his voice. Time limit is 1 second, and memory limit is 64MB. –  Pilgrim To Programming Mar 21 at 19:57
Does "after him" mean "not including him", or does it mean "only people sitting to his right"? –  user2357112 Mar 22 at 10:10

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

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

-
For the i++ comment, I don't think it is still relevant nowadays as any half decent compiler should go for the best option. –  Josay Mar 21 at 20:14
@Josay it's still worth knowing, even just so you understand the underlying differences. Even when the performance concerns are taken away, I still consider it a minor point of correctness. If you want to do task x, but you're actually doing x + y, that's not quite the same thing. And I'm one of those people who doesn't like to assume certain optimization a will be made :). –  Corbin Mar 21 at 20:20
That's fair enough :-) –  Josay Mar 21 at 20:47

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.

-
Very nice, these were my initial thoughts, but now I think I've got an O(n log n) solution. I'll try to formulate it. –  iavr Mar 22 at 10:31
Forget about the previous comment. I now saw the solution by kkongas. –  iavr Mar 22 at 11:06

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

-
Excellent! I was thinking of an O(n log n) solution but you saved me the effort! –  iavr Mar 22 at 11:04

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;
}
}

-
Wow, +1! I don't know why a map didn't occur to me in my dynamic programming algorithm. That would allow the chair-wise algo instead of the much more complicated person one with a minimal performance hit. –  Corbin Mar 22 at 0:30

# Typedefs as an alternative to new types

As others have mentioned, single letter variables are a detriment to readability. One way to help this is of course to add new types. As Corbin mentioned, adding a class or struct to hold just two ints can be a bit overkill (personally I don't mind). I'm not sure if this is considered good practice, but what I do in these situations is to create an alias:

typedef int seat;
typedef int voice;
typedef std::pair<seat, voice> scientist;


Or using the hash solution:

typedef std::map<seat, voice> congress;


Some editors may even help you by showing the type of the alias, rather than the underlying type.

# Extracting code to functions to improve singularity of purpose

Finally, as has been mentioned before, it's helpful to extract each level of nesting into a little function. Not only is it easier on the eye, you can give each extracted piece of code it's own name. That helps to reason about what each step in an algorithm is doing as well.

For example the first for loop is really just initializing a big old vector. I would move that whole loop into a function called parse_input or something and then move the second big loop into a function called calculate_number_of_people_participating or something a little snappier. And then maybe even have it return a new list or perhaps update its input and extract the printing section (cout << r << endl;) to a different function as well. I know that its not quite as compact and also slightly (but not in a big OhO sort of way) inefficient, but it separates each section of code into what is logically doing. Some pseudo code to illustrate:

typedef int seat;
typedef int voice;
typedef std::map<seat, voice> scientists;

scientists parse_input();
int calculate_people_participating(const scientists& participants);
void print_people_participating(int number);

int main() {
participants = parse_input();
number_of_people_participating = calculate_people_participating(participants);
print_people_participating(number_of_people_participating);
return 0;
}
`

Probably the names are a bit too verbose* and your algorithm may not make them quite as appropriate, but I hope you get the idea.

* I don't mind long names for top level functions you call only once.

-