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

forest
New poster
Posts: 11
Joined: Sat Sep 02, 2006 5:13 pm
Contact:

11080 - Place the Guards

Post by forest »

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

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by 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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by 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
New poster
Posts: 11
Joined: Sat Sep 02, 2006 5:13 pm
Contact:

Post by forest »

Nazmul Quader Zinnuree wrote: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
New poster
Posts: 11
Joined: Sat Sep 02, 2006 5:13 pm
Contact:

Post by forest »

mamun wrote: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
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

help

Post by vinay »

what should be the approach for it...

when to return -1...
Cycle of odd length ???
If I will myself do hashing, then who will do coding !!!

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

Re: help

Post by Martin Macko »

vinay wrote: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
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

@marko

Post by vinay »

And for the other cases ?

DFS???
:oops:
If I will myself do hashing, then who will do coding !!!

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

Re: @marko

Post by Martin Macko »

vinay wrote:And for the other cases ?

DFS???
:oops:
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
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

final hint please

Post by vinay »

n/2 ??
If I will myself do hashing, then who will do coding !!!

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

Re: final hint please

Post by Martin Macko »

vinay wrote: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
New poster
Posts: 11
Joined: Sat Sep 02, 2006 5:13 pm
Contact:

Re: final hint please

Post by 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
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by 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
Last edited by kp on Sat Sep 02, 2006 11:24 pm, edited 1 time in total.

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

Re: final hint please

Post by Martin Macko »

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.
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

think about bipartite graphs.
The tricky case is:

Code: Select all

1
1 0
The output should be 1 instead of 0.

Post Reply

Return to “Volume 110 (11000-11099)”