Dance party by 3 Idiots (Algorithm Intensive Programming Challenge)

Points: 30

Imperial College of Engineering is holding a dance contest as a part of one of the events of its cultural fest. The contest consists of a duet (team of 2) performance by participants. There were a total of 2N applicants for the contest and now, it is the turn of the organizers to form N pairs among these participants.

Since none of the 2N participants know each other, the organizers decide to form pairs such that it will be easy for the members of a pair to get acquainted with each other. The patron of the organizing team, Mr. Viru Sahasrabuddhi, popularly known as Virus, decides to give this task as an assignment to one of the members of the organizing team, Raju. Virus despises Raju and hence assigns this apparently difficult task to him.

He asks Raju to form pairs such that the overall sum of residential distances between members of all of the N participating pairs is the minimum possible value. In other words, if a1,a2,..an are the residential distances between members of first, second...and nth pair respectively, then (a1+a2+...an) should be minimum.

He also threatens Raju to expel him from the university, if later, others can make a pair formation with the overall pair distance sum less than that found by Raju. Raju is perplexed by the assignment and is totally stumped. Rancho, a very close friend of his who is also a good programmer, comes to his help and solves his problem with ease.

Can you determine what C/CPP code did Rancho write?

Input format

Input to the program consists of a series of lines. The first line contains a number N indicating the number of pairs to be formed. Each of the next 2N lines consist of two integers representing x and y co-ordinates of residential locations of 2N applicants on a co-ordinate plane.

Output format

Print a single integer, the minimum overall sum of distances between members of pairs rounded to the nearest integer as output.

Limits & Points

• N<=5, Time Limit : 3.5 Sec, Points: 5
• N<=25, Time Limit : 3 Sec, Points: 10
• N<=100, Time Limit : 3 Sec, Points: 15

Server specification of the Judge

• Processor: Intel Core 2 Duo T5300 (1.73 GHZ)
• RAM: 1 GB
• Compiler: gcc/g++ (Only C/CPP codes are allowed)

Sample Input

5
20 20
40 20
10 10
2 2
240 6
12 12
100 120
6 48
12 18
0 0

Sample Output

237

Solution

Problem Statement:
The Problem can be clearly stated as: Given n pair of points in two dimensional space, join each vertex with exactly one another vertex such that it forms a Perfect Matching with total weight as minimum. Prefect Matching appears when each vertex is joined to only one other vertex. This problem is also known as Minimum Weight Perfect Matching [1].

Brute Force Approach:
A straight forward appraoch to this problem would be, number the vertices from 0 to 2n-1, find all possible permutations of the numbers, and match adjacent vertices. From all these matchings, select the one with minimum cost.

But it produces redundant matching permutations giving same pairing multiple times For eg: Permutations like 0 1 2 3 4 5 7 6 8 9, 0 1 2 3 4 5 8 9 7 6, 0 1 2 3 4 5 8 9 6 7 etc. will have same total cost.

Further improvement to this solution can be done by avoiding above situation. For this, we first make all possible pairs and calculate distance corresponding distance for each pair. Next we sort this list in ascending order of pairs according to distance between pairing points. Then we select n pairs from this list, such that no vertex appears in two pairs and find cost for this match. Similarly, find cost for other matchings and select the one with minimum cost.

Finding Mimimum Weight Perfect Matching in Polynomial time:
Edmond's Blossom algorithm solves the problem of Minimum Weight Perfect Matching in Polynomial time. It is based upon the linear programming formulation of the problem described clearly in [1].

Edmond's Algorithm:

1. Input the points and Initialize radius of disk for each vertex to be zero. Initially there are no Blossom or Moat and set L of tight edges and M of perfect match are empty.
2. If all the outermost discs and moats are married, then M gives the perfect matching. Otherwise select one of the outermost discs/moats as tree root.
3. Expand/shrink all of the trees until one of the following happens:
   • Case 1: The width of a shrinking moat W goes to zero. Here the blossom of W dissolves. Some of the disc/moats surrounded by W will replace W in T ; these disc/moats form a path which is chosen in such a way that the new tree is still alternating. One or two tight edges in the dissolving blossom will leave L. Repeat step 2.
   • Case 2: An expanding disc/moat R from one of the trees T collides with another outermost disc/moat R . Add to L the edge joining the two colliding points.
     • Subcase 2.1: Both R and R belong to the same tree T . Here we make a new blossom B by tracing back toward the root of T starting from both R and R to find the odd cycle disc/moats that will form B. A new moat W having width zero surrounds all the disc/moats in B. Modify T by replacing all the disc/moats within B by the new moat W . Repeat step 2.
     • Subcase 2.2: The disc/moat R is either unmarried or (belongs to a different tree T = T ). Go to step 3.
4. We now find an augmenting path joining the unmarried point in the root of T to the unmarried point in R (or in the root of T ). Traverse T from R, back toward its root. If a blossom is encountered in this traversal, then we traverse around it in whatever direction makes an alternating path. (If another tree T is involved in the collision, then we do the same for T , and joint the two traversals together to obtain the alternating path.) Finally we augment the matching M along this path. Dismantle the trees structures T (and T ), leaving a set of married pairs of outermost disc/moats. Go to step 1.

This algorithm solves the problem in O(n4), n being number of vertices. Stepwise desription with terminologies is given in [1]. In past years Edmond's algorithm has been studied by a number of researcher and many efficient polynomial time algorithms have been proposed in the literature to solve this problem. [3] includes a new implementation by Cool and Rohe along with a report on various available algorithms for solving the problem and their corresponding complexities, most of which are improvements of Edmond's algorithm.

Blossom V is another efficient implementation of minimum cost perfect matching whose source code and associated document can be found at [4].

References:

1. Edmonds’ Minimum Weight Perfect Matching Algorithm
2. Linear Programming
3. Computing Minimum Weight Perfect Matching
4. Blossom V: A new Implementation of Minimum Cost Perfect Matching

Look for hints and post your queries at the CodeWarrior forum thread Round 1-Dance party by 3 Idiots(Algorithm)