TopCoder problem "OlympicGames" used in TCO08 Round 4 (Division I Level Two)



Problem Statement

    

There are N teams taking part in The Programming Olympic Games. They are numbered by integers between 0 and N-1, inclusive. According to the rules, the Games consist of many competitions. The three top scoring teams within each competition are awarded gold, silver and bronze medals. Within a single competition, there can be no ties, and a single team can win at most one medal. After the Games are over, the following rules are used to rank the teams:

  1. If two teams each have a different number of gold medals, the team with more gold medals is ranked higher. Otherwise, the next rule is used.
  2. If two teams each have a different number of silver medals, the team with more silver medals is ranked higher. Otherwise, the next rule is used.
  3. If two teams each have a different number of bronze medals, the team with more bronze medals is ranked higher. Otherwise, the lower numbered team is ranked higher.

The Games are now in progress and left competitions are left before the Games are over. You are given a String[] medals, the i-th element of which represents the current number of medals won by the i-th team. Each element is formatted "GOLD SILVER BRONZE" (quotes for clarity), where GOLD is the number of gold medals, SILVER is the number of silver medals, and BRONZE is the number of bronze medals.

Team 0 is very strong in the disciplines represented by all of the remaining competitions. Therefore, they will definitely win gold medals in all of them. Return the worst possible final ranking for team 0, where 1 is the highest ranking, 2 is the second highest, and so on.

 

Definition

    
Class:OlympicGames
Method:worstPlace
Parameters:String[], int
Returns:int
Method signature:int worstPlace(String[] medals, int left)
(be sure your method is public)
    
 

Notes

-The total number of gold medals, silver medals and bronze medals in the input will not necessary be equal to each other. This is because some medals in past competitions may have been cancelled. However, in each of the remaining competitions, all three medals will be awarded with no cancellations.
 

Constraints

-medals will contain between 3 and 50 elements, inclusive.
-Each element of medals will be formatted "GOLD SILVER BRONZE" (quotes for clarity), where GOLD, SILVER and BRONZE are integers between 0 and 10,000, inclusive, with no extra leading zeros.
-left will be between 0 and 10,000, inclusive.
 

Examples

0)
    
{"0 0 0",
 "1 0 0",
 "1 0 0"}
1
Returns: 3
Team 0 will win gold in the one remaining competition, and the other two teams will win silver and bronze. Each team ends up with one gold medal, but since team 0 has no other medals, it will end up in 3rd place.
1)
    
{"0 0 0",
 "1 0 0",
 "1 0 0"}
2
Returns: 1
Team 0 will end up with two gold medals, which is more than either of the other teams, so the silver and bronze medal counts don't matter here.
2)
    
{"1 2 3",
 "100 0 0",
 "7 0 0",
 "7 0 0",
 "7 0 0",
 "7 0 0"}
6
Returns: 4
Team 0 is guaranteed to rank lower than team 1 (because of gold medals). If two of the remaining four teams each wins 3 silvers, team 0 will rank lower than them as well.
3)
    
{"0 7 6",
 "6 0 0",
 "6 1 1"}
6
Returns: 1
Team 2 would need 6 silver and 6 bronze medals to rank higher than team 0. Since it's impossible to win more than one medal in a single competition, this cannot happen, so team 0 is guaranteed to rank the highest.
4)
    
{"0 5 5",
 "5 0 0",
 "5 0 10"}
5
Returns: 2
Team 2 can rank higher than team 0 if it gets 5 silvers.
5)
    
{"0 1 1",
 "3 0 0",
 "3 0 0",
 "3 0 1",
 "3 1 0",
 "3 1 1",
 "3 1 1"}
3
Returns: 5
The following would be the worst scenario for team 0: Team 3 wins 2 silver medals, team 4 wins 2 bronze medals, team 5 wins 1 silver, and team 6 wins 1 bronze. Team 0 would rank 5th.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12014&pm=8610

Writer:

ivan_metelsky

Testers:

PabloGilberto , vorthys , Olexiy

Problem categories:

Dynamic Programming