11080 - Place the Guards

[forest]

Getting WA. Could you give some 'tricky' tests ?

[Nazmul Quader Zinnuree]

Input

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

Output

Code: Select all

1
2
1
-1
3

[mamun]

Input

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

Output

Code: Select all

3
3
1

[forest]

Input

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

Output

Code: Select all

1
2
1
-1
3

I guess there is some error as examples 3 and 4 contain vertex number out of range. All other tests pass.

[forest]

Input

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

Output

Code: Select all

3
3
1

Getting same results. Could some1 give an example of a solution that gets ACCEPTED.

[vinay]

what should be the approach for it...

when to return -1...
Cycle of odd length ???

[Martin Macko]

what should be the approach for it...

when to return -1...
Cycle of odd length ???

Yes, if the graph contains a cycle of odd length as a subgraph, you should write -1.

[vinay]

And for the other cases ?

DFS???

[Martin Macko]

And for the other cases ?

DFS???

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]

n/2 ??

[Martin Macko]

n/2 ??

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.

[forest]

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.

[kp]

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

[Martin Macko]

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.

Consider the following graph: 0-1, 2-1, 1-3, 3-4 and 3-5. It's maximum matching is 2, but you need 3 guards.

[sclo]

think about bipartite graphs.
The tricky case is:

Code: Select all

1
1 0

The output should be 1 instead of 0.