SRM 700, D1, 300-Pointer (FindingFriend)

James S. Plank

Wed Oct 26 01:05:22 EDT 2016
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:

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:

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:

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:

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. */
}