TCO 2017, Round 1A, 250-Pointer (PingPongQueue)

James S. Plank

Wed Apr 5 00:59:56 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2017
Competitors who opened the problem: 883
Competitors who submitted a solution: 783
Number of correct solutions: 626
Accuracy (percentage correct vs those who opened): 70.9%
Average Correct Time: 22 minutes, 32 seconds.

The constraints here are small enough that you can simulate the ping pong competition, and at the end of your simulation, you return the two competitors.

The challenge, from a programming point of view, is what data structures you should use for the ping pong table, and for the queue of waiting competitors. I'm going to suggest that you use a set for the table. When there are two competitors, the size of the set will be two, and since the skill levels are all different, the loser will be the first element of the set, and the winner will be the second element (which is the last element). That's nice.

For the queue, I suggest either a list or a deque. The reason is that you are always pushing to the back and popping off the front. Both the list and deque data structures support those operations in constant time.

With those data structures, you simply simulate the system, and at the end, you create the return vector from the set.

Let's walk through Example 1, where the skills vector is {1, 2, 3}, N is 2 and K is four. What you do is turn the skills vector into a queue (a deque or a list). You'll keep track of the last "winner" and the number of consecutive games that the winner has won. We'll initialize those to -1 and 0. Here's the state of the system before any games are played:

Queue = { 1, 2, 3 }.   Table = {}.    Last-winner = -1.  Consecutive = 0.  Games-played = 0.

Now, we play the first game -- while the table size is less than two, pop a player off the front of the queue, and insert the player into the table. Here's the state of our system after this step:

Queue = { 3 }.   Table = { 1, 2 }.    Last-winner = -1.  Consecutive = 0.  Games-played = 0.

Now, we look at the table to see who won, and update the stats:

Queue = { 3 }.   Table = { 1, 2 }.    Last-winner = 2.  Consecutive = 1.  Games-played = 1.

At this point, we need to prepare for the next game. We erase the loser from the table, and push it to the back of the queue. If the winner has won its threshold of games, you do the same with the winner. Here, the winner has only won one consecutive game, so we don't do anything with the winner. Here's the state of the system:

Queue = { 3, 1 }.   Table = { 2 }.    Last-winner = 2.  Consecutive = 1.  Games-played = 1.

Now, we play the second game -- while the table size is less than two, pop a player off the front of the queue, and insert the player into the table:

Queue = { 1 }.   Table = { 2, 3 }.    Last-winner = 2.  Consecutive = 1.  Games-played = 1.

Three is the winner -- we'll erase two from the set, and then update the stats:

Queue = { 1, 2 }.   Table = { 3 }.    Last-winner = 3.  Consecutive = 1.  Games-played = 2.

Now the third game -- 1 goes from the queue to the table:

Queue = { 2 }.   Table = { 1, 3 }.    Last-winner = 3.  Consecutive = 1.  Games-played = 2.

Three wins, so we move 1 to the queue and update the stats. Since 3 has now won two consecutive games, we also move 3 to the queue. Here's the state of the system:

Queue = { 2, 1, 3 }.   Table = { }.    Last-winner = 3.  Consecutive = 2.  Games-played = 3.

Time to start game 4 -- 2 and 1 are moved to the table, and we update the stats:

Queue = { 3 }.      Table = { 1, 2 }.  Last-winner = 2.  Consecutive = 1.  Games-played = 4.

Since the number of games played equals K, we're done -- we return 1 and 2.