SRM 700, D1, 300-Pointer (FindingFriend)

James S. Plank

Wed Oct 26 01:05:22 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: October, 2016
Competitors who opened the problem: 254
Competitors who submitted a solution: 234
Number of correct solutions: 126
Accuracy (percentage correct vs those who opened): 49.6%
Average Correct Time: 27 minutes, 14 seconds.

This is one of those Topcoder problems that falls into the class of "Run through a vector keeping track of the correct information." The challenge is figuring out what information to keep track of. These problems can be frustrating, because they don't follow a classic algorithm like DFS or Enumeration. Instead, you have to reason through it.

So, let's start with step 1 -- sorting the leaders vector. You know that when you do so:

leaders[0] will equal 1.
leaders[1] will be a number between 2 and roomSize+1.
leaders[2] will be a number between leaders[1]+1 and roomSize*2+1.
Etc.

Now, let's consider leaders[1]. You know that the contestents who placed between two and (leaders[1]-1) must be in room 0 (the room corresponding to leaders[0]). If leaders[1] equals (roomSize+1), then room 0 will be completely full of contestants who all score better than the contestants in room 1. Otherwise, room 0 will have leftover contestants who will score below leaders[1]. We're going to keep track of leftover, and the number of rooms that have room for leftover contestants, and that will help us answer the problem as we run through the leaders vector.

It's probably best to give a concrete example, and I'm going to make one up rather than use the Topcoder examples. In my example, we'll have:

roomSize equals 10.
leaders is already sorted, and it equals { 1, 6, 16, 31, 32 }.
We'll consider multiple values of friendPlace: 1, 3, 7, 30, 31 and 33.

Before we go through our algorithm, let's knock out a special case -- if friendPlace equals a value in leaders, then the answer is one. We'll write that code first.

Then, we're going to run through the leaders vector, and while we do so, we're going to keep track of a few values:

r is the room number that we're looking at. This will start with zero.
leftover is the number of contestants that can go into rooms less than r. This will also start with zero.
rooms is the number of rooms less than r into which those contestants can go. Once again, this starts with zero.

Our algorithm is going to start by incrementing r. So, in the first iteration, r is incremented to one. As we increment r, we also increment rooms, because we have added room (r-1) to the number of rooms less than r into which contestants can go. Plus, we increment leftover by (roomSize-1), because those are the number of places left in room (r-1) into which contestants can go.

We then consider friendPlace. If it is less than leaders[r], but greater than leaders[r-1], then it has to go into one of those rooms less than r. So we return rooms.

Otherwise, we consider the value (leaders[r]-(leaders[r-1]-1)). This is the number of contestents that must go into a room less than r. To reflect this, we decrement leftover by this number. As a final step, if leftover is now zero, then all of the rooms less than r are full -- we need to set rooms to zero to reflect that there is no room.

And then we continue. When we're done with the algorithm, it's possible that friendPlace is greater than all of the values of leaders. In that case, we return turn the final value of room plus one (to account for the last room).

Let's run the algorithm on our example:

r	leaders[r]	leftover before we look at friendPlace	rooms before we look at friendPlace	Return value if friendPlace is less than leaders[r]	leftover after we look at friendPlace	rooms after we look at friendPlace
0	1	0	0	Impossible	0	0
1	6	0+9=9	1	1	9-(6-1-1)=5	1
2	16	5+9=14	2	2	14-(16-6-1)=5	2
3	31	5+9=14	3	3	14-(31-16-1)=0	Since leftover==0: 0
4	32	0+9=9	1	1	9+(32-31-1)=9	1

So, given the table above:

When friendPlace equals 1, you return 1, because it matches leaders[0].
When friendPlace equals 3, you return 1, which is the value of rooms when r=1.
When friendPlace equals 7, you return 2, which is the value of rooms when r=2.
When friendPlace equals 30, you return 3, which is the value of rooms when r=3.
When friendPlace equals 31, you return 1, because it matches leaders[3].
When friendPlace equals 33, you return 2, which is the value of (rooms+1) at the end of the loop. You do this when friendPlace is greater than all of the leaders.

I'm sure this is not the only way to do this problem, but it is a good exercise for you in reasoning through what information to maintain as you run through a vector, and how you use that information to calculate the proper return value.

My Solution. I have it commented below:

int FindingFriend::find(int roomSize, vector <int> leaders, int friendPlace)
{
    /* These are the three variables described in the writeup. */

    int r;
    int leftover;
    int rooms;

    /* The first step is sorting, and checking to make return one when 
       friendPlace equals one of the leaders. */
      
    sort(leaders.begin(), leaders.end());

    for (r = 0; r < leaders.size(); r++) {
      if (friendPlace == leaders[r]) return 1;
    }

    /* We set r, leftover and rooms before we start our main algorithm. */

    r = 0;
    leftover = 0;
    rooms = 0;

    while (1) {

        /* First step -- increment r, and if our loop is done, return (rooms+1). */

        r++;
        if (r == leaders.size()) return rooms+1;

        /* Now, we're adding the number of available contestant slots from room r-1
           into leftover, and incrementing rooms to reflect adding room r-1 */

        leftover += (roomSize-1);
        rooms++;

        /* If friendPlace is less than the leader for room r, then your friend has
           to go into one of the previous rooms.  Return rooms. */

        if (friendPlace < leaders[r]) return rooms;

        /* Decrement leftover by the number of contestants that must go into a
           room less than r.  If that number is now zero, then we need to set 
           rooms to zero, because there are no slots left in any of those rooms. */

        leftover -= (leaders[r]-leaders[r-1]-1);
        if (leftover == 0) rooms = 0;
    }

    return 0;                                     /* Shut the compiler up. */
}