Tennis tournament P73160


pdf   zip


Consider a tennis tournament with m participants with names x1, x2, …, xm, where m is a power of two. In the first round x1 plays against x2, x3 plays against x4, …, and xm − 1 plays against xm. The players that lose are eliminated, and the process is repeated with the remaining players. When only a player remains, this is the winner of the tournament.

For instance, let m = 8, and suppose that in the first round x1 defeats x2, x3 loses against x4, x5 defeats x6, and x7 defeats x8. In the second round x1 plays against x4 (suppose that x4 wins), and x5 plays against x7 (suppose that x7 wins). In the third and last round x4 plays against x7. Assuming that x4 wins, this is the champion. The following figure shows the championship just described:

Write a procedure that, given the names of the players and the table of results, returns the name of the winner of the tournament:

string winner(const vector<string>& name, const vector<bool>& win);

The vector name has size m, where m is any power of 2. For each j between 0 and m − 1, we have name[j] = xj + 1. All the names are different.

For instance, this could be the table of names of the tournament previously described:

The vector win has size m − 1 and contains all the results of the matches: the first round is stored in the last m/2 positions, the second round is stored in the m/4 previous positions, the third round is stored in the m/8 previous positions, …, and the result of the last round (the final) is stored in win[0]. The boolean of each position indicates if the first player (the one with the smallest index) has won against the second one.

This would be the table of results of the tournament previously described:

For the example tournament, the answer should be “Borg”.

Observation You only need to submit the required procedure; your main program will be ignored.

Salvador Roura
Carlos Molina
Original language
Other languages
Official solutions
User solutions