TournamentPlan
SRM 324 · 2006-10-25 · by AdrianKuegel
Problem Statement
A city will host a round-robin tournament, where each competitor plays each of the other competitors exactly once. The city can be seen as an orthogonal grid, with streets in the east-west direction and avenues in the north-south direction. Each game must be played between two competitors at an intersection. You must determine the locations and ordering of the games that will minimize the total distance travelled by all the competitors.
You are given two
Constraints
- street will contain between 1 and 50 elements, inclusive.
- avenue will contain the same number of elements as street.
- Each element of street and avenue will be between 0 and 1000000, inclusive.
{0,2,0,2,1}
{0,0,2,2,1}
Returns: 8
One possible solution is to have competitor 0 play competitor 2 (competitor indices are 0-based) at intersection (0,1). Then have competitor 1 play competitor 3 at intersection (2,1). Then schedule all the other games at intersection (1,1). Here's one possible ordering: Game 1 (Competitor 0 vs. Competitor 2) -------------------------------------- Competitor 0 goes from (0,0) to (0,1): 1 Competitor 2 goes from (0,2) to (0,1): 1 Game 2 (Competitor 1 vs. Competitor 3) -------------------------------------- Competitor 1 goes from (2,0) to (2,1): 1 Competitor 3 goes from (2,2) to (2,1): 1 Game 3 (Competitor 0 vs. Competitor 1) -------------------------------------- Competitor 0 goes from (0,1) to (1,1): 1 Competitor 1 goes from (2,1) to (1,1): 1 Game 4 (Competitor 2 vs. Competitor 3) -------------------------------------- Competitor 2 goes from (0,1) to (1,1): 1 Competitor 3 goes from (2,1) to (1,1): 1 At this point, all the competitors are at (1,1) so no further travel is necessary for the remaining games. The sum of all the distances is 8.
{0,1000000}
{1000000,0}
Returns: 2000000
One possible solution is to organize the game at intersection (500000, 500000).
{0,1,1,3}
{2,5,1,2}
Returns: 7
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}
{0,0,0,0,0,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,0,0,0,0,0,0,0,0,0,0,0,0}
Returns: 50000000
the maximum return value
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}
{0,0,0,0,0,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,0,0,0,0,0,0,0,0,0,0,0,0}
Returns: 48000000
In this example, intersection (0,0) is optimal, which is very far from the avarage of the numbers (480000, 480000).
{0}
{0}
Returns: 0
With only one competitor, no game is needed.
Submissions are judged against all 116 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TournamentPlan with a public method int getTravelDistance(vector<int> street, vector<int> avenue) · 116 test cases · 2 s / 256 MB per case