Canadian Computing Olympiad: 2013 Day 1, Problem 2
Don Cherry has been hired to run 24-hour coverage of a series of single-elimination, bracket-style, furniture disassembly tourneys (tournaments). Each competitor has a furniture disassembly skill level, an integer between and . In every head-to-head match, the competitor with the larger skill level wins and moves on, while the other is eliminated from the tourney. It is guaranteed that, at any time, the skill levels of all competitors are distinct, so there are no ties.
There are () competitor positions in the tourney tree, numbered from left to right. In the first round, competitors and face off in a furniture disassembly race, as do competitors and , etc. In each subsequent round, the winners of the first two matches from the previous round compete, as do the winners of the following two, etc. After rounds, a single winner remains. For example, when , the tourney tree looks like this:
where represents the winner of the match between competitors and , represents the winner of the match between competitors and , and represents the winner of the match between and . The winner of this tourney is .
Because of sponsorship contracts, some competitors will be replaced over time. After any new person comes in, a new tourney is held.
In order to help Don Cherry, you must write a program to compute certain tourney statistics at various points in time, given a sequence of () commands — see the input format below.
The first line of input contains two integers, () and (), separated by one space.
The next lines, for from to , each contain one integer , indicating the skill level of the initial competitor at position in the tourney tree.
Each of the following lines will be a command in one of three formats:
- means that the competitor at position is removed, and replaced with a new one with skill level . A tourney should then be held.
- means that your program should determine who won the current tourney. Print the position (between and ) of this competitor.
- means that your program should print out the number of rounds that the competitor at position won in the current tourney.
For each or command in the input, print out the corresponding integer on a line by itself.
2 8 30 20 10 40 S 1 W R 4 9 S 4 W R 2 35 S 2 W
1 4 0 1 2 2
The results of the initial tourney are as follows:
As can be seen, competitor wins match, and competitor wins the entire tourney. After this, competitor is replaced by a new competitor with skill level . As can be seen below, this causes a different outcome for the tourney held after the third command:
Finally, the state of the tourney tree after the next competitor replacement (caused by the sixth command) is: