TopCoder problem "TournamentPlan" used in SRM 324 (Division I Level Two)



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 int[]s, street and avenue, where (street[i], avenue[i]) is the intersection where the ith competitor is initially located. The distance between intersection (x,y) and intersection (x2,y2) is |x-x2| + |y-y2|. The competitors do not have to return to their starting locations after their last games. Return the minimum possible sum of all the distances that must be travelled by the competitors in this tournament.

 

Definition

    
Class:TournamentPlan
Method:getTravelDistance
Parameters:int[], int[]
Returns:int
Method signature:int getTravelDistance(int[] street, int[] avenue)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{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.
1)
    
{0,1000000}
{1000000,0}
Returns: 2000000
One possible solution is to organize the game at intersection (500000, 500000).
2)
    
{0,1,1,3}
{2,5,1,2}
Returns: 7
3)
    
{0}
{0}
Returns: 0
With only one competitor, no game is needed.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10004&pm=6807

Writer:

AdrianKuegel

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Sorting