11080 - Place the Guards

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

Moderator: Board moderators

andre_abrantes
New poster
Posts: 3
Joined: Mon Jun 05, 2006 4:44 am
Location: Rio de Janeiro, Brasil

Post by andre_abrantes » Thu Sep 07, 2006 8:11 pm

Hello everyone!
I've tried all the input avaliable in this thread and my code seems to work with them, except for that one from mamud, I think, where there are edges that connect vertexes beyond the limit previously given.
Anyway, I just keep getting WA.
Here is my code, can anyone tell me where is my mistake!?

Code: Select all

Corrected and accepted!
Thanks to Martin Macko.
Thanks in advance.
Last edited by andre_abrantes on Sun Sep 10, 2006 11:36 pm, edited 1 time in total.
Andr

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Sep 09, 2006 8:48 pm

andre_abrantes wrote:Hello everyone!
I've tried all the input avaliable in this thread and my code seems to work with them, except for that one from mamud, I think, where there are edges that connect vertexes beyond the limit previously given.
Anyway, I just keep getting WA.
Here is my code, can anyone tell me where is my mistake!?
Not working for:

Code: Select all

1
5 6
0 1
0 2
1 3
2 3
4 0
5 0
The correct answer:

Code: Select all

2

andre_abrantes
New poster
Posts: 3
Joined: Mon Jun 05, 2006 4:44 am
Location: Rio de Janeiro, Brasil

Post by andre_abrantes » Sun Sep 10, 2006 11:37 pm

Thank you Martin Macko.
I found out that my code could push the same vertex twice or more in the queue.
Andr

max_zd
New poster
Posts: 2
Joined: Tue Apr 10, 2007 2:51 pm

Help!

Post by max_zd » Tue Apr 10, 2007 3:06 pm

Is there anybody who can help me? :(

I think my algorithm is correct, but keeps get WA.

My algoirthm:
1. Process each connected components("CC") one by one
2. For each CC, if there is only one vertex belongs to it, then the answer is increased by 1. if there are more than one vertex belong to it, we check if it is a bipartite graph, if not, we assert that the problem is no solution. otherwise, we count the number of vertices in set X and set Y. obviously, we choose the smaller between them.

Here is my code.

Code: Select all

#include <cstdio>
#include <cstring>

const	int		limit_size	=	200	+	10;

int			n , m;
bool			mat	[ limit_size ][ limit_size ];
int			cnt	[ 2 ];

void	init()
{
	int		i , a , b;

	memset(mat , 0 , sizeof(mat));

	scanf("%d%d" , &n , &m);
	for(i = 0; i < m; i ++)
	{
		scanf("%d%d" , &a , &b);
		mat[a][b] = mat[b][a] = 1;
	}
}

bool			mark	[ limit_size ];
int			color	[ limit_size ];
int			queue	[ limit_size ];
int			head , tail;

bool	check()
{
	int		i , j;

	for(i = 0; i <= tail; i ++)
		for(j = i + 1; j <= tail; j ++)
			if( mat[ queue[i] ][ queue[j] ] && color[ queue[i] ] == color[ queue[j] ] ) return 0;
	return 1;
}

void	solve()
{
	int		i , u , v;
	int		ret = 0;

	memset(mark , 0 , sizeof(mark));

	for(i = 0; i < n; i ++)
		if(! mark[i])
		{
			cnt[0] = cnt[1] = 0;

			queue[ head = tail = 0 ] = i;
			mark[i] = 1; color[i] = 0; cnt[0] = 1;

			while(head <= tail)
			{
				u = queue[ head ++ ];

				for(v = 0; v < n; v ++)
					if(mat[u][v] && ! mark[v])
					{
						queue[ ++ tail ] = v;
						mark[v] = 1; color[v] = 1 - color[u]; cnt[ color[v] ] ++;
					}
			}

			if(tail == 0) 
			{
				ret ++; continue ;
			}

			if(! check())
			{
				printf("-1"); return ;
			}
			ret += cnt[0] <? cnt[1];
		}

	printf("%d\n" , ret);
}

int	main()
{
	int		cnt_case;

	for(scanf("%d" , &cnt_case); cnt_case --;)
	{
		init();
		solve();
	}

	return 0;
}

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: Help!

Post by windows2k » Sun Apr 29, 2007 4:17 am

max_zd wrote:

Code: Select all


			if(! check())
			{
				printf("-1"); return ;
			}
You should modifiy printf("-1") to printf("-1\n")
THis works

Ratul Ahmed
New poster
Posts: 4
Joined: Mon Aug 30, 2010 3:40 am

11080 - Place the Guards

Post by Ratul Ahmed » Fri Mar 04, 2011 2:36 pm

simple Bipertite graph problem...

1) make 2 sets of vertex for each sub-graph or graph
2) take the minimum vertices from each of those sets & sum it
3) check how many vertices has no adjacent (help the king to find the minimum number of guards needed to guard all the junctions and streets of his country. )
4) sum it with answer

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11080 : algorithm

Post by Mukit Chowdhury » Mon Oct 01, 2012 1:49 pm

Cut after Accepted !!!

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 11080 : algorithm

Post by alexiago » Wed Aug 14, 2013 7:05 pm

One more tip, the input may not contain edges for all vertexes, so vertexes with grade = 0 should be counted to the answer.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 11080 : algorithm

Post by vsha041 » Thu Mar 20, 2014 9:54 pm

Some useful test cases

Input

Code: Select all

1
5 3
0 1
3 2
2 1
Output

Code: Select all

3
Input

Code: Select all

1
1 0
Output

Code: Select all

1
Output is 3 because junction 4 needs to be guarded as well and other than that you can place guards at 0 and 2.

To solve this problem just check if it is bipartite or not? But remember that graph could be disconnected so you will have to take that into account as well. Now if a graph is bipartite, just count the nodes in both subsets and choose the miminum. I used distances (even and odd) to divide the graph into two sets of nodes.

samir_h
New poster
Posts: 11
Joined: Wed Mar 18, 2015 8:47 am

11080 - Place the Guards[uDebug output different for TC sequence change]

Post by samir_h » Fri Mar 25, 2016 12:03 pm

In uDebug getting different output if we change the test case sequence.
For example: input [2, input#1, input#2] = output[o#1, o#2] but input[2, input#2, input#1] giving output[o#2, o#3]
Why ?

--------------------------------------------------------------
Input:
2

5 6
0 1
0 2
1 3
2 3
4 0
5 0

13 12
0 8
1 8
2 9
3 9
4 10
5 10
6 11
7 11
8 12
9 12
10 12
11 12

Output:
2
4
--------------------------------------------------------------
Input(replace 2nd input with 1st input):
2

13 12
0 8
1 8
2 9
3 9
4 10
5 10
6 11
7 11
8 12
9 12
10 12
11 12

5 6
0 1
0 2
1 3
2 3
4 0
5 0

Output:
4
-1

--------------------------------------------------------------

samir_h
New poster
Posts: 11
Joined: Wed Mar 18, 2015 8:47 am

Re[Ratul Ahmed]: 11080 - Place the Guards

Post by samir_h » Fri Mar 25, 2016 12:06 pm

Hello Ratul Ahmed,
I followed your approach:
1) make 2 sets of vertex for each sub-graph or graph
2) take the minimum vertices from each of those sets & sum it
3) check how many vertices has no adjacent (help the king to find the minimum number of guards needed to guard all the junctions and streets of his country. )
4) sum it with answer

But still Wrong Answer.
My code: http://ideone.com/fork/QQgE7x

Can any one suggest what is wrong ?

Post Reply

Return to “Volume 110 (11000-11099)”