PROBLEM STATEMENT
We all know that the red-rated TopCoder members are good, but because they are
all so close at the top it is hard to truly rank them. So TopCoder wants to
hold a standard single elimination winner-take-all tournament among only the
red members to see who is the true champion. However, this creates a problem.
In a single elimination tournament, every competitor competes against one
other. The winner moves on and the loser is finished. Therefore, each round
eliminates half of its contestants. As a result of this, to end up with a
single champion, every round must have a number of contestants equal to a power
of two. For example, the NCAA March Madness tournament traditionally starts
with 64 competitors, and then drops to 32, 16, 8, 4, 2, and then finally one
champion. But because red status is only determined by rating, there may not be
a number of coders equal to an even power of two. In that case, byes (automatic
wins) must be given to some coders in the first round to make sure that the
next round follows the power of two rule. For example, if there are 14 coders
in a round, the next lowest power of 2 is 8, so there must be 8 coders in the
next round. To fill those slots, 12 coders can play as normal filling up 6
slots in the next round. But to fill the 7th and 8th slots, 2 coders must be
given byes. The byes are given to the coders with the top ratings because they
have earned it with their incredible ratings. If there is a tie in rating when
assigning byes, the bye will be given to the coder who appears first in coders.
Create a class Tournament that contains the method giveByes that takes in a
String[] representing coders and their ratings, and returns a String[]
containing the names of the coders who get byes. The return String[] must be
sorted in descending order by rating. In case multiple coders share the same
rating, the one that comes earlier in coders will come first. If no byes are
needed, return a String[] containing only the entry "NO BYES NEEDED".
DEFINITION
Class: Tournament
Method: giveByes
Parameters: String[]
Returns: String[]
Method signature (be sure your method is public): String[] giveByes(String[]
coders);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- coders will contain between 1 and 50 elements inclusive.
- Each element of coders will contain between 3 and 50 characters inclusive.
- Each element of coders will be in the format "name rating".
- Each element of coders will contain exactly one space.
- Each name will contain only lower case and capital letters ('a'-'z' inclusive
and 'A'-'Z' inclusive).
- Each name will be unique.
- Rating will be a number between 1 and 9999 inclusive.
- Rating may have leading zeroes.
EXAMPLES
Quotes are used for clarity and are not actually part of the input.
Example 1: coders = {"dmwright 2914","reid 2995","NDBronson 2959","SnapDragon
3005"}
There are four contestants, which is an even power of two, so no byes are needed.
Return {"NO BYES NEEDED"}
Example 2: coders = {"a 1000"}
If a is the only eligible contestant, then he is automatically the champion and
there is no need for byes.
Return {"NO BYES NEEDED"}
Example 3: coders = {"SnapDragon 3005","reid 2995","NDBronson 2959"}
To end up with two coders in the next round, two coders compete as normal, and
one is granted a bye. That bye goes to SnapDragon for having the highest rating.
Return {"SnapDragon"}
Example 4: coders = {"reid 2995","NDBronson 2959","SnapDragon 3005"}
These are the same coders as in the last example, but in a different order.
Regardless, SnapDragon is still the highest rated coder, and is given the bye.
Return {"SnapDragon"}
Example 5: coders = {"ZorbaTHut 2873","dmwright 2914","reid 2995","NDBronson
2959","SnapDragon 3005"}
With 5 coders, two compete as normal and three get byes, leaving four in the
next round.
Return {"SnapDragon","reid","NDBronson"}
Example 6: coders = {"a 1000","b 100","c 3000","d 1","e 3000","f 3000"}
There are six coders, so two need byes. However, c, e, and f are all tied at
3000. Because c and e come first, they get the byes.
Return {"c","e"}
Example 7: coders = {"leading 0010","zeroes 0987","with 0001","byes 0256","here
0999"}
Return {"here","zeroes","byes"}
Example 8: coders = {"a 1","b 2","c 3","d 4","e 5","f 6","g 7","h 8","i 9","j
10","k 11","l 12","m 13","n 14","o 15","p 16","q 17","r 18","s 19","t 20","u
21","v 22","w 23","x 24","y 25","z 26","A 27","B 28","C 29","D 30","E 31","F
32","G 33","H 34","I 35","J 36","K 37","L 38","M 39","N 40","O 41","P 42","Q
43","R 44","S 45","T 46","U 47","V 48","W 49","X 50"}
Return {"X","W","V","U","T","S","R","Q","P","O","N","M","L","K"}