TopCoder problem "SoccerFan" used in TCHS SRM 63 (Division I Level Three)



Problem Statement

    

You are tracking the results of a soccer tournament. For each match that has been played so far, you have written down the names of the two opposing teams, along with the number of goals scored by each team. However, you suspect that for one of the matches, you may have written down the wrong number of goals scored by one of the teams.

Fortunately, you know which team is the current tournament leader. The tournament is scored as follows. For each game, the winning team (the team that scored more goals) gets 3 points and the losing team gets 0 points. If there is no winner (both teams scored the same number of goals), each team gets 1 point. The tournament leader is the team that has strictly more points than any other team.

You are given a String[] results, where the i-th element is what you have written down as the result of the i-th match. Each element is formatted as "team1 team2 a:b" (quotes for clarity), where team1 is the name of the first team, team2 is the name of the second team, a is the number of goals scored by the first team, and b is the number of goals scored by the second team. You are also given a String winner, the name of the current tournament leader according to the real results.

If, according to your written results, the tournament leader is winner, return -2. Otherwise, if there exists exactly one match in your written results where you can change the number of goals scored by one of the teams, and the tournament leader would then be winner according to the changed written results, return the index of that match. If there exist several such matches, return the index of the earliest of those matches. If no such match exists, return -1. All indices are 0-based.

 

Definition

    
Class:SoccerFan
Method:whereIsMistake
Parameters:String[], String
Returns:int
Method signature:int whereIsMistake(String[] results, String winner)
(be sure your method is public)
    
 

Constraints

-results will contain between 1 and 50 elements, inclusive.
-Each element of results will contain between 7 and 50 characters, inclusive.
-Each element of results will be formatted as "team1 team2 a:b" (quotes for clarity).
-In each element of results, team1 and team2 will each contain between 1 and 43 lowercase letters ('a'-'z'), inclusive.
-In each element of results, a and b will each be a single digit ('0'-'9').
-In each element of results, team1 and team2 will be distinct.
-winner will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
 

Examples

0)
    
{"real bayer 2:2"}
"bayer"
Returns: 0
According to your written results, the one match resulted in a draw. This means there is no tournament leader (both teams have 1 point). To make "bayer" the tournament leader, we can change the number of goals scored by "bayer" in that match to 3.
1)
    
{"breda ajax 2:2", "breda psv 0:0", "psv ajax 1:1"}
"ajax"
Returns: 0
Here, every match has resulted in a draw according to your written results, so there is no tournament leader (each team has 2 points). To make "ajax" the leader, we can change either match 0 or match 2. We return the smallest among these two matches.
2)
    
{"borussia shalke 4:2", "bayer herta 3:2","bayer bavaria 5:2"}
"borussia"
Returns: -1
According to your written results, "bayer" has 6 points, "borussia" has 3 points, and "shalke", "herta" and "bavaria" have 0 points. You cannot increase the score for "borussia" by changing 1 match. You can decrease the score for "bayer" to 3 points, but that is not enough to make "borussia" the leader.
3)
    
{"spartak real 2:1", "real spartak 3:2"}
"spartak"
Returns: 1
Both "real" and "spartak" have 3 points. Changing match 0 can't increase the score for "spartak", so we need to change match 1.
4)
    
{"xy yx 3:2", "xx yy 1:1"}
"yx"
Returns: 0
We can, for example, change match 0 to 1:2.
5)
    
{"borussia shalke 4:2", "bayer herta 3:2","bayer bavaria 5:2", "borussia verder 1:1"}
"borussia"
Returns: 1
Even though "borussia" didn't play in match 1, we can change its result to decrease the final score for "bayer" and thus make "borussia" the leader.
6)
    
{"spartak dinamo 3:2","dinamo rubin 2:2"}
"spartak"
Returns: -2
"spartak" has 3 points, and "dinamo" and "rubin" have 1 point each. "spartak" is the leader without any changes.
7)
    
{"a b 9:0"}
"c"
Returns: -1
8)
    
{"a b 0:0", "a c 1:1", "g d 3:1"}
"a"
Returns: 0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13532&pm=10206

Writer:

DStepanenko

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simple Math, Simple Search, Iteration, Simulation