10911 - Forming Quiz Teams

Monsoon · 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]

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

is there any dp solution to this problem ?

wook · 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)

Larry · 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

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

sohel · 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 · 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

, 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;
}

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

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

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

Thank you. You are right.

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

OJ Board

10911 - Forming Quiz Teams

dp..

Re: dp..

same here..

10911 - Forming Quiz Teams