10911  Forming Quiz Teams
Moderator: Board moderators
Re: dp..
about dp solution, whose complexity is about O(2^n * n^2)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..

 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:
and I get:
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
Code: Select all
Case 1: 1492.91
Case 2: 1519.71
Case 3: 1293.73
Case 4: 1290.51
Case 5: 1344.81
Check out http://www.algorithmist.com !
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 )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..
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 sofar best solution, break.
I don't think that there will be a correct greedy solution... but then, I may be wrong
same here..
The judge solution was exactly implemented using this procedure.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 sofar best solution, break.
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.
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.
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()
{
char cad[LEN];
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;
}
10911  Forming Quiz Teams
I'm considering using a tree to represent the matchings, and solve it by DFS+pruning.
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.
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)
I stay home. Don't call me out.
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...
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...
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 (n1) different persons. You don't need to try every pair.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..
Regards
Sanny

 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.
Check out http://www.algorithmist.com !