TopCoder problem "TheSoccerDivOne" used in SRM 453 (Division I Level Three)

Problem Statement


John and Brus have an interest in team sports tournaments. They are investigating a soccer tournament that is currently in progress. Soccer is a team sport played between two teams of eleven players using a spherical ball. It is the most popular football variant worldwide, and is widely considered to be the most popular sport in the world.

In this tournament, each game results in either a victory for one team or a draw. If a team wins a game, it gains three 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. Each pair of teams can play against each other any number of times.

You are given a int[] points representing the current standings in the tournament. The i-th element of points is the score of the i-th team. You can assume that the points represent a valid state, i.e., intermediate standings that can be achieved in a tournament according to the rules described above.

Each team will play exactly four more games in the tournament, but it is not known what the matchups will be. This means that every distribution of the remaining games is potentially possible. In particular, the same pair of teams might play more than one game against each other. After the tournament is over, the teams will be ranked by score. 1st place will go to the team with the highest score, 2nd place will go to the team with the second highest score, and so on. If two teams have the same score, the team with the lower number will place higher. For example, if team 0 and team 3 each have the highest score of 100 points, then team 0 will place 1st and team 3 will place 2nd.

John's favorite team is team 0, and he wants it to place as high as possible. Assuming that the remaining games can be scheduled arbitrarily and can end with any possible outcome, return the highest possible place for team 0 at the end of the tournament.



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.
-points will represent a valid state.


{5, 17}
Returns: 1
If team 0 wins all its remaining games, it will end up with a score of 17. Team 1 will also have 17 points, but according to the tie breaker rules, team 0 will get first place.
{5, 18, 21, 19}
Returns: 4
John's favorite team has too few points here to rise above last place.
{4, 1, 5}
Returns: 1
It will be easy for John's favorite team to get to the top of the standings after the remaining games.
{4, 16, 4, 16, 16}
Returns: 2

Problem url:

Problem stats url:




PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Dynamic Programming