TopCoder problem "TheTournamentDivTwo" used in SRM 453 (Division II Level One)

Problem Statement


John and Brus have an interest in team sports tournaments. They are currently investigating the intermediate standings of a tournament. They don't know which games have been played so far. They only know that the tournament is played using the following rules:

Each game is played between two teams and results in either a victory for one team or a draw. If a team wins a game, it gains two points and its opponent gains no points. In case of a draw, each team gains one point. The score of a team is the sum of all the points it has gained from all its games. There are no restrictions on which teams can play against each other, and each pair of teams can play against each other any number of times (possibly zero).

You are given a int[] points representing the intermediate standings of the tournament. The i-th element of points is the score of the i-th team. Return the minimum number of games that could have been played to achieve those standings. If points doesn't represent a valid state, return -1 instead.



Method signature:int find(int[] points)
(be sure your method is public)


-points will contain between 2 and 50 elements, inclusive.
-Each element of points will be between 0 and 1,000,000, inclusive.


{10, 1, 1}
Returns: 6
Here the first team has five wins or four wins and two draws. The second and the third team each has one draw.
{1, 1, 1}
Returns: -1
These standings are impossible. For each of the three teams to have one point, each one must have played in a game that resulted in a draw. There is no way for three teams to have each played in exactly one game.
{0, 0, 0, 0, 0, 0, 0}
Returns: 0
There are no points, which means no games have been played yet.
{13, 8, 7}
Returns: 14

Problem url:

Problem stats url:




PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Simple Math, Simple Search, Iteration