10911 - Forming Quiz Teams

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Sat Sep 24, 2005 11:05 am

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]

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

dp..

Post by sohel » Sun Sep 25, 2005 2:46 pm

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..

Post by wook » Sun Sep 25, 2005 3:37 pm

sohel wrote:is there any dp solution to this problem ?
about dp solution, whose complexity is about O(2^n * n^2)


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:

Post by Larry » Wed Sep 28, 2005 11:37 pm

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

Post by misof » Thu Sep 29, 2005 12:16 am

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 :)

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

same here..

Post by sohel » Thu Sep 29, 2005 10:26 am

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

Post by neno_uci » Wed Oct 19, 2005 2:55 am

Hi:

I tried to implement a solution using that explanation..., but I get TLE :cry: , 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;
}

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

10911 - Forming Quiz Teams

Post by ImLazy » Thu Oct 20, 2005 12:10 pm

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

Post by misof » Thu Oct 20, 2005 12:33 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...

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

Post by ImLazy » Sat Oct 22, 2005 9:38 am

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:

Post by Sanny » Sat Oct 22, 2005 4:21 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..
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:

Post by Moha » Wed Jul 05, 2006 3:26 pm

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:

Post by Moha » Fri Jul 07, 2006 1:00 am

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:

Post by Moha » Sun Jul 23, 2006 2:45 am

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:

Post by Larry » Thu Sep 07, 2006 5:41 pm

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.

Post Reply

Return to “Volume 109 (10900-10999)”