TopCoder problem "CheatABit" used in TCO05 Qual 7/8 (Division I Level Three)



Problem Statement

    

NOTE: This problem statement contains an image that may not display properly if viewed outside of the applet.

You have written several chess programs and want to have a tournament with them. All your programs have ratings, which entirely determine the result of each game (the player with a higher rating always wins).

Before the tournament all programs are placed in a list. You want to put yourself somewhere in this list (the total number of participants including you will be a power of 2). In every round, the first participant in the list plays the second, the third plays the fourth, and so on. Players who lose their games are eliminated and removed from the list, while the winners advance to the next round. In the next round the process is repeated with the list of winners. The tournament lasts until only one player (the winner of the tournament) is left.

For example, if players participating in the tournament have ratings {100, 300, 200, 150}, then Player 1 plays Player 2 and Player 3 plays Player 4. Players 2 and 3 win and meet in the final, where Player 2 wins.



You want to win the tournament at any price, so you enter a game winning cheat code whenever you lose. However, you want to cheat as rarely as possible. You need to find the place in the initial list which allows you to win the tournament with as few cheat codes as possible. You will be given the ratings of all the programs, in the order they are placed in the list. Given yourRating as well, return the minimal number of codes you must enter to win the tourney.
 

Definition

    
Class:CheatABit
Method:enterCodes
Parameters:int[], int
Returns:int
Method signature:int enterCodes(int[] ratings, int yourRating)
(be sure your method is public)
    
 

Constraints

-ratings will have 1, 3, 7, 15 or 31 elements.
-Each element of ratings will be between 1 and 3000, inclusive.
-ratings will not contain duplicate elements.
-yourRating will be between 1 and 3000, inclusive.
-yourRating will not be equal to any element of ratings.
 

Examples

0)
    
{1, 2, 3, 4, 6, 7, 8}
5
Returns: 1
One of the best strategies is to place yourself after player 2. In the first round you win over the player with rating 3, in the second round you will succeed against the player with rating 2, and only in the final will you need to cheat.
1)
    
{100, 200, 300}
301
Returns: 0
You win the tournament without any cheating.
2)
    
{100, 200, 300}
50
Returns: 2
You must cheat twice.
3)
    
{100, 1, 99, 2, 98, 3, 97, 4, 96, 5, 95, 6, 94, 7, 93}
50
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4673

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8026&pm=4673

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Recursion, Simple Math