## 10911 - Forming Quiz Teams

Moderator: Board moderators

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
You have very silly mistake

look at your best variable, why you only once give it value inf, there are multiple case so you should give it inf before each test
[btw if you still have wa try to give inf bigger number]

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### dp..

is there any dp solution to this problem ?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### Re: dp..

sohel wrote:is there any dp solution to this problem ?

dy[A] means the minimum cost for matching teams,
only considering the people in set A (note that |A| : even number)
Sorry For My Poor English..

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I'm doing the n^2 * 2^n DP, but getting WA, can someone give me some output for these cases:

Code: Select all

``````8
A 886 383
B 915 777
C 335 793
D 492 386
E 421 649
F 27 362
G 59 690
H 926 763
I 426 540
J 736 172
K 368 211
L 429 567
M 530 782
N 123 862
O 135 67
P 802 929
8
A 58 22
B 167 69
C 456 393
D 42 11
E 373 229
F 919 421
G 537 784
H 324 198
I 370 315
J 526 413
K 980 91
L 873 956
M 170 862
N 281 996
O 925 305
P 327 84
8
A 505 336
B 729 846
C 857 313
D 895 124
E 545 582
F 367 814
G 364 434
H 750 43
I 808 87
J 178 276
K 584 788
L 651 403
M 399 754
N 60 932
O 368 676
P 12 739
8
A 586 226
B 539 94
C 570 795
D 378 434
E 601 467
F 902 97
G 492 317
H 756 652
I 280 301
J 441 286
K 689 865
L 619 444
M 729 440
N 117 31
O 771 97
P 675 481
8
A 927 709
B 856 567
C 353 497
D 965 586
E 683 306
F 624 219
G 871 528
H 829 732
I 19 503
J 368 270
K 715 708
L 149 340
M 723 796
N 245 618
O 451 846
P 555 921
0``````
and I get:

Code: Select all

``````Case 1: 1492.91
Case 2: 1519.71
Case 3: 1293.73
Case 4: 1290.51
Case 5: 1344.81
``````

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Anonymous wrote:Nevermind, got it accepted after declaring hypot in the header.

I got AC in more than 3 seconds.. is there a greedy way to do it or something? The times were really fast..
I assume that due to the geometric nature of this task a cleverly pruned backtracking should be really fast. (In the contest I wrote a similar DP solution as you mentioned, so I can't tell for sure )

What should be enough:
- when searching for a match to a person, always try the available ones in increasing distance order
- as soon as the current sum exceeds the so-far best solution, break.

I don't think that there will be a correct greedy solution... but then, I may be wrong

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### same here..

misof wrote: What should be enough:
- when searching for a match to a person, always try the available ones in increasing distance order
- as soon as the current sum exceeds the so-far best solution, break.
The judge solution was exactly implemented using this procedure.

I got the idea of this problem, while trying to solve a chinese postman problem..
.. this is very similar to 'minimum matching cost', that is done in chinese postman problem.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Hi:

I tried to implement a solution using that explanation..., but I get TLE , could you gurus take a look to my code, thanx in advance,

Yandry.

Code: Select all

``````#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX 16
#define LEN 25

struct punt
{
int x, y;
};

struct pepe
{
int num;
double dis;
};

int k, i, j, n;
int mark[MAX], testNum;
struct punt punt1[MAX];
struct pepe matr1[MAX][MAX];
double m;

void Avanza(int, double);

int sort(const void *a, const void *b)
{
struct pepe *aa = (struct pepe*)a;
struct pepe *bb = (struct pepe*)b;

return (aa->dis <= bb->dis) ? -1 : 1;
}

void BuscaPareja(int aQuien, int parejas, double dist)
{
int a, b;
double c;

if (m != -1.0 && dist >= m)
return;

for (a = 0; a < 2 * n; a++)
{
if (m != -1.0 && dist >= m)
return;

b = matr1[aQuien][a].num;

if (!mark[b])
{
c = matr1[aQuien][a].dis;
mark[b] = 1;

if (parejas + 1 < n && (m == -1 || m > dist + c))
Avanza(parejas + 1, dist + c);
else
{
if (m == -1.0 || dist + c < m)
m = dist + c;
}

mark[b] = 0;
}
}
}

void Avanza(int parejas, double dist)
{
int a;

for (a = 0; a < 2 * n; a++)
{
if (m != -1.0 && dist >= m)
return;

if (!mark[a])
{
mark[a] = 1;
BuscaPareja(a, parejas, dist);
mark[a] = 0;
}
}
}

int main()
{

scanf("%d", &n);
testNum = 0;

while (n)
{
for (k = 0; k < 2 * n; k++)
scanf("%s %d %d", &cad, &punt1[k].x, &punt1[k].y);

for (i = 0; i < 2 * n; i++)
for (j = i; j < 2 * n; j++)
{
matr1[i][j].num = j;
matr1[i][j].dis = sqrt(
(punt1[i].x - punt1[j].x) * (punt1[i].x - punt1[j].x)
+
(punt1[i].y - punt1[j].y) * (punt1[i].y - punt1[j].y));

matr1[j][i].num = i;
matr1[j][i].dis = matr1[i][j].dis;
}

for (k = 0; k < 2 * n; k++)
{
qsort(matr1[k], 2 * n, sizeof(struct pepe), sort);
mark[k] = 0;
}

m = -1.0;
Avanza(0, 0.0);

//puts("...");

printf("Case %d: %0.2lf\n", ++testNum, m);
scanf("%d", &n);
}

return 0;
}
``````

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### 10911 - Forming Quiz Teams

I'm considering using a tree to represent the matchings, and solve it by DFS+pruning.

Code: Select all

``````               (1,2)
--------------+--------------
/     /     /     \     \     \
(3,4) (3,5) (3,6) (4,5) (4,6) (5,6)
|     |     |     |     |     |
(5,6) (4,6) (4,5) (3,6) (3,5) (3,4)

(3,4)
--------------+--------------
/     /     /     \     \     \
(1,2) (1,5) (1,6) (2,5) (2,6) (5,6)
|     |     |     |     |     |
(5,6) (2,6) (2,5) (1,6) (1,5) (1,2)

(5,6)
--------------+--------------
/     /     /     \     \     \
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)
|     |     |     |     |     |
(3,4) (2,4) (2,3) (1,4) (1,3) (1,2)``````
But,you see, there are repeated branches(like (1,2)->(3,4)->(5,6) and (3,4)->(1,2)->(5,6) and (5,6)->(1,2)->(3,4)). Who can tell me how to avoid them? Thank you.
I stay home. Don't call me out.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Consider the pairs in lexicographic order only. I.e., represent the pair {a,b} by an ordered pair (a,b) with a<b, pairs with a lower 1st coordinate go earlier.

E.g., if N=6, the first pair may be (1,2), (1,3), (1,4), (1,5) or (1,6). If you choose (1,4) to be the first pair, the second pair may be (2,3), (2,5) or (2,6). And so on...

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Thank you. You are right.
I stay home. Don't call me out.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
Anonymous wrote:Nevermind, got it accepted after declaring hypot in the header.

I got AC in more than 3 seconds.. is there a greedy way to do it or something? The times were really fast..
My timing was .082 sec. I used O(2^n* n) DP. When dividing the original problem into subproblems, you only need to match only one person with (n-1) different persons. You don't need to try every pair.

Regards
Sanny

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
I want to know is there any solution exist with Weighted matching? I think we can solve this problem easily with WM, but why the problem range is so small? am i correct?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
For Larry`s testcases I got :
• Case 1: 1472.90
Case 2: 1275.61
Case 3: 1293.73
Case 4: 1173.44
Case 5: 1094.64
Is that correct?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
No All of Larry's testcase are correct. My WM-modelling was incorrect. Now I got it!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Ya, my things are right. I was Guest up there, and it turns out I forget to declare hypot (otherwise it returns int on the judge). Whoops.