11080  Place the Guards
Moderator: Board moderators
11080  Place the Guards
Getting WA. Could you give some 'tricky' tests ?

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:
Input
Output
Code: Select all
5
1 0
2 0
3 2
1 2
2 3
3 3
1 2
2 3
1 3
13 10
0 5
5 4
5 3
5 2
5 1
5 6
7 8
7 9
7 10
7 11
Code: Select all
1
2
1
1
3
Input
Output
Code: Select all
3
5 2
0 1
2 3
5 3
0 1
2 3
1 3
4 3
2 0
2 1
2 3
Code: Select all
3
3
1
I guess there is some error as examples 3 and 4 contain vertex number out of range. All other tests pass.Nazmul Quader Zinnuree wrote:InputOutputCode: Select all
5 1 0 2 0 3 2 1 2 2 3 3 3 1 2 2 3 1 3 13 10 0 5 5 4 5 3 5 2 5 1 5 6 7 8 7 9 7 10 7 11
Code: Select all
1 2 1 1 3
Getting same results. Could some1 give an example of a solution that gets ACCEPTED.mamun wrote:InputOutputCode: Select all
3 5 2 0 1 2 3 5 3 0 1 2 3 1 3 4 3 2 0 2 1 2 3
Code: Select all
3 3 1
help
what should be the approach for it...
when to return 1...
Cycle of odd length ???
when to return 1...
Cycle of odd length ???
If I will myself do hashing, then who will do coding !!!

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: help
Yes, if the graph contains a cycle of odd length as a subgraph, you should write 1.vinay wrote:what should be the approach for it...
when to return 1...
Cycle of odd length ???

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: @marko
Think about it. If you have a conected graph with no odd cycles as subgraphs, what are the only possibilities you can place guards, so they guard everything and do not interfere.vinay wrote:And for the other cases ?
DFS???

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: final hint please
Actually not, consider the graph K1,7 (complete bipartite graph with one vertex in the first partition and seven vertices in the second partition). It has 8 vertices, and just one gruard is enough.vinay wrote:n/2 ??
Re: final hint please
I programmed maximum matching and was sure it is correct, but can not get my solution AC. Wish i new what is my problem and why there were so many resubmitions during the contest.
Problem can be solved without maximum matching.
Just think about bipartite graph and it's connected
components.
Edit: example of useless of maximum matching:
1
8 7
0 5
1 5
2 5
3 5
1 4
1 6
1 7
answer should be 4, but MM=2
Just think about bipartite graph and it's connected
components.
Edit: example of useless of maximum matching:
1
8 7
0 5
1 5
2 5
3 5
1 4
1 6
1 7
answer should be 4, but MM=2
Last edited by kp on Sat Sep 02, 2006 11:24 pm, edited 1 time in total.

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: final hint please
Consider the following graph: 01, 21, 13, 34 and 35. It's maximum matching is 2, but you need 3 guards.forest wrote:I programmed maximum matching and was sure it is correct, but can not get my solution AC. Wish i new what is my problem and why there were so many resubmitions during the contest.
think about bipartite graphs.
The tricky case is:
The output should be 1 instead of 0.
The tricky case is:
Code: Select all
1
1 0