TopCoder problem "MLBRecord" used in TCO04 Round 2 (Division I Level Three)



Problem Statement

    

In Major League Baseball, there is a regular season of games where teams play each other, and at the end of the season, the teams with the best records go on to compete in the playoffs. Better records are indicated by more wins. For this problem, we'll assume that the teams which go to the playoffs are the teams with the best records, and that there are no division champion berths.

During the regular season, it is possible for a team to "clinch" a spot in the playoffs by getting enough wins such that no matter what happens in the remaining games, the team makes the playoffs. Similarly, it is also possible for a team to be eliminated from the playoffs if its record is so poor that no matter what happens, it cannot claim a playoff spot. If it is possible for two or more teams to end in a tied record, and the record is good enough to claim at least one playoff spot, but there are not enough playoff spots for all the tied teams, then those teams can neither clinch nor be eliminated. See example 4.

Given a int[] wins (the number of wins each team has), an int gamesLeft (how many games each team has left to play), and an int N (the number of playoff spots available), determine which teams have clinched one of the spots in the playoffs, and which teams have been eliminated. Each team will play gamesLeft games against other teams in the league, but you should assume that each game could be against any other team. Of course, teams cannot play themselves, and each team must play the same number of games. The return value should be a String, where the character at position i represents the status of element i in wins. Each character should be a capital 'C' if the team has clinched, a capital 'E' if it has been eliminated, or a period '.' if the team has neither clinched, nor been eliminated.

 

Definition

    
Class:MLBRecord
Method:teamStatus
Parameters:int[], int, int
Returns:String
Method signature:String teamStatus(int[] wins, int gamesLeft, int N)
(be sure your method is public)
    
 

Constraints

-wins will have between 3 and 50 elements, inclusive.
-Each element in wins will be between 0 and 100, inclusive.
-gamesLeft will be between 0 and 100, inclusive.
-N will be between 2 and the number of elements in wins - 1, inclusive.
-The elements in wins will be constructed such that the values would be achievable with each team playing the same number of games, and all games being played only between teams in the list.
-gamesLeft multiplied by the number of elements in wins will be an even number.
 

Examples

0)
    
{10,5,7,2}
4
2
Returns: "C..E"
Two spots are available for the playoffs and each team has played 12 games. With 4 games left per team, it is possible for team 2 to beat or tie team 0, but it is not possible for two teams to beat or tie team 0, so team 0 has clinched a spot. Neither team 1 nor team 2 has clinched because they cannot be sure the other will not beat them out. Even if team 3 wins all of their games, they cannot make it into the playoffs.
1)
    
{1,1,1,3,4,5}
3
3
Returns: ".....C"
2)
    
{26,12,93,31,74,35,59,99,21}
40
4
Returns: ".EC....C."
3)
    
{26,12,93,31,74,35,59,99,21}
22
4
Returns: "EECECECCE"
Might as well cancel the rest of the season.
4)
    
{10, 10, 10}
0
2
Returns: "..."
All the teams ended in a tied record after playing 20 games each. Because only two teams can make the playoffs, we cannot say whether any of the teams have clinched or have been eliminated.
5)
    
{27, 40, 33, 20, 40}
20
2
Returns: "....."

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5879&pm=2236

Writer:

schveiguy

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Brute Force, Greedy, Simple Search, Iteration