So, let's start with step 1 -- sorting the leaders vector. You know that when you do so:
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:
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:
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.
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. */ } |