Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1852
You have been given the job of forming the quiz teams for the next ‘MCA CPCI Quiz Championship’.
There are 2 ∗ N students interested to participate and you have to form N teams, each team consisting
of two members. Since the members have to practice together, all the students want their members
house as near as possible. Let x1 be the distance between the houses of group 1, x2 be the distance
between the houses of group 2 and so on. You have to make sure the summation (x1 +x2 +x3 +. . .+xn)
is minimized.
Input
There will be many cases in the input file. Each case starts with an integer N (N ≤ 8). The next 2 ∗ N
lines will given the information of the students. Each line starts with the students name, followed by
the x coordinate and then the y coordinate. Both x, y are integers in the range 0 to 1000. Students
name will consist of lowercase letters only and the length will be at most 20.
Input is terminated by a case where N is equal to 0.
Output
For each case, output the case number followed by the summation of the distances, rounded to 2 decimal
places. Follow the sample for exact format
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int N, target;
double dist[20][20], memo[1 << 16]; // 1 << 16 = 2^16, note that max N = 8
// O(N*2^(2N))
double matching(int bitmask) {
if (memo[bitmask] > -0.5)
return memo[bitmask];
if (bitmask == target)
return memo[bitmask] = 0;
double ans = 2000000000.0;
int p1, p2;
// find first bit that is not set
for (p1 = 0; p1 < 2 * N; p1++)
if (!(bitmask & (1 << p1)))
break;
// try all other bit that is not set
for (p2 = p1 + 1; p2 < 2 * N; p2++)
if (!(bitmask & (1 << p2)))
ans = min(ans, dist[p1][p2] + matching(bitmask | (1 << p1) | (1 << p2)));
return memo[bitmask] = ans;
}
int main() {
int i, j, caseNo = 1, x[20], y[20];
while (scanf("%d", &N), N) {
for (i = 0; i < 2 * N; i++)
scanf("%*s %d %d", &x[i], &y[i]);
// distance between all pairs
for (i = 0; i < 2 * N - 1; i++)
for (j = i + 1; j < 2 * N; j++)
dist[i][j] = dist[j][i] = hypot(x[i] - x[j], y[i] - y[j]);
for (i = 0; i < (1 << 16); i++) memo[i] = -1.0; // set -1 to all cells
target = (1 << (2 * N)) - 1; // all set
printf("Case %d: %.2f\n", caseNo++, matching(0));
}
}
Input
sohel 10 10
mahmud 20 10
sanny 5 5
prince 1 1
per 120 3
mf 6 6
kugel 50 60
joey 3 24
limon 6 9
manzoor 0 0
derek 9 9
jimmy 10 10
0
Output
Case 2: 1.41
Demonstration
UVA Online Judge solution -10911-Forming Quiz Teams - UVA Online Judge solution in C,C++,java