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 » Sat Sep 02, 2006 5:20 pm

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 » Sat Sep 02, 2006 5:34 pm

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 » Sat Sep 02, 2006 5:35 pm

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 » Sat Sep 02, 2006 9:14 pm

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 » Sat Sep 02, 2006 9:16 pm

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.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

help

Post by vinay » Sat Sep 02, 2006 9:37 pm

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

User avatar
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 » Sat Sep 02, 2006 9:42 pm

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.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

@marko

Post by vinay » Sat Sep 02, 2006 9:45 pm

And for the other cases ?

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

User avatar
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 » Sat Sep 02, 2006 10:19 pm

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.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

final hint please

Post by vinay » Sat Sep 02, 2006 10:24 pm

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

User avatar
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 » Sat Sep 02, 2006 10:36 pm

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 » Sat Sep 02, 2006 10:40 pm

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 » Sat Sep 02, 2006 11:19 pm

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.

User avatar
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 » Sat Sep 02, 2006 11:20 pm

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 » Sun Sep 03, 2006 8:07 am

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)”