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
{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.
{100, 200, 300}
301
Returns: 0
You win the tournament without any cheating.
{100, 200, 300}
50
Returns: 2
You must cheat twice.
{100, 2, 3, 4, 5, 6, 7, 101, 102, 103, 104, 105, 106, 107, 180}
50
Returns: 2
{2}
1
Returns: 1
{1}
2
Returns: 0
{100, 1, 99, 2, 98, 3, 97, 4, 96, 5, 95, 6, 94, 7, 93}
50
Returns: 4
{1, 99, 2, 98, 3, 97, 4, 96, 5, 95, 6, 94, 7, 93, 100}
50
Returns: 3
{100, 1, 99, 2, 98, 3, 97, 4, 96, 5, 95, 6, 94, 7, 8}
50
Returns: 3
{1900}
2241
Returns: 0
{850, 189, 1466, 1114, 586, 2286, 1284, 133, 869, 2031, 2978, 451, 1827, 2560, 43}
374
Returns: 3
{1196, 798, 2050, 1004, 2367, 451, 601}
96
Returns: 3
{2662, 1139, 118, 2681, 268, 1780, 271, 1020, 2493, 1232, 2886, 711, 223, 1168, 102, 1558, 2688, 2661, 1414, 2955, 617, 2618, 1984, 196, 153, 2226, 1424, 2857, 2844, 423, 2533}
1719
Returns: 3
{837, 813, 830, 2815, 2897, 2346, 1804}
2055
Returns: 1
{57, 2222, 2547}
2910
Returns: 0
{643, 2531, 1998, 1724, 2895, 2347, 345}
2020
Returns: 2
{740}
716
Returns: 1
{223, 800, 611, 2340, 2821, 1688, 670, 181, 1949, 2971, 1500, 2200, 2945, 1588, 2231}
2811
Returns: 2
{68, 1729, 598, 89, 453, 382, 542, 188, 2580, 1502, 2797, 203, 2939, 2563, 2326}
703
Returns: 2
{2958, 386, 2611}
1715
Returns: 2
{345, 2206, 2827, 1357, 2506, 2634, 1832, 2013, 1511, 893, 1980, 951, 1441, 552, 2343}
1871
Returns: 3
{2127, 2376, 2428, 917, 1763, 1931, 2253, 603, 1053, 2852, 2214, 2152, 445, 811, 45}
2285
Returns: 2
{273, 1442, 2326, 1895, 2937, 2774, 1151}
2878
Returns: 1
{563, 2243, 1428, 1380, 78, 143, 1498}
756
Returns: 2
{1775, 2232, 2904}
353
Returns: 2
{1911, 1153, 1196, 1968, 2085, 482, 608, 160, 1619, 2713, 866, 1756, 2803, 510, 1827}
46
Returns: 4
{1475, 1736, 2094}
296
Returns: 2
{2904, 372, 282, 2382, 1667, 1604, 2846, 2738, 1401, 1758, 881, 2303, 728, 856, 2017}
1566
Returns: 3
{872, 1182, 2218, 1641, 1976, 769, 2546}
428
Returns: 3
{2493, 864, 1527, 1599, 438, 2256, 71, 168, 2733, 2552, 1423, 2579, 2111, 859, 8}
2609
Returns: 1
{1356, 2979, 497, 451, 1669, 843, 2045}
2351
Returns: 1
{399, 1528, 892, 537, 2915, 2737, 242}
2067
Returns: 1
{2114, 1134, 1338, 802, 2320, 638, 1495, 1333, 2517, 1082, 1590, 1272, 2397, 2591, 1197, 1901, 736, 1473, 146, 1735, 814, 407, 2895, 426, 2761, 2533, 1547, 1377, 131, 1680, 1047}
876
Returns: 4
{1707, 1105, 1164, 1221, 1062, 56, 2639, 2292, 1813, 1344, 2211, 1392, 1699, 2953, 1103, 2042, 93, 2894, 3, 711, 906, 409, 2452, 746, 880, 264, 228, 1334, 1837, 2575, 2356}
615
Returns: 4