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

ivan.cu
New poster
Posts: 21
Joined: Sun Mar 19, 2006 7:50 pm
Location: Cuba

Some test cases!

Post by ivan.cu » Sun Sep 03, 2006 10:27 am

Some one can give me test cases such not work for the greedy algorithm:

Code: Select all

1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.

if exist unvisited street print -1
else print guards
Some help please!!!

ivan

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sun Sep 03, 2006 12:38 pm

Thanks for sclo and Martin Macko, I got AC at last !!

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

Post by vinay » Sun Sep 03, 2006 2:13 pm

me too... Thanks to martin and kp... :lol:
If I will myself do hashing, then who will do coding !!!

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

bipartite

Post by vinay » Sun Sep 03, 2006 2:17 pm

By the way I would be blessed to get some useful links on Graphs, speciallly bipartite and its properties. Also some links for maximum matching algorithm... ohh the list is already too long.. :lol:

please someone forward it if possible :oops:
If I will myself do hashing, then who will do coding !!!

hector-chang
New poster
Posts: 3
Joined: Sun Sep 03, 2006 4:14 pm

I have an idea and a WA

Post by hector-chang » Sun Sep 03, 2006 4:49 pm

Hello!

Based in the following observations I thinked the next solution.

Observation: Once you put a guard in some vertex there is only one admisible configuration of guards for the rest of the connected componet of the graph to which this vertex belongs (One can see this by a BFS starting in this vertex, taking care to guard all the edges). Since every edge must be guarded and there are only two possibilities to guard a particular edge there are at most two admisible configuration of guards for each connected component.

Solution: The problem is now reduced to each connected component and there are at most two numbers to calculate in every one. With a BFS it can be traversed the connected components and then calculated the numbers that I mention.

This program can solve the test cases from this forum and from the original problem in a correct way. However I have WA.

There is a flaw in this algorithm? If anybody wants to see the code I could send it

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

correct algo

Post by vinay » Sun Sep 03, 2006 4:59 pm

The algo is correct...
for each connected component find the minimum no. of guards...
return the sum of all guards of all components...

Check this I/O :

Code: Select all

1
1 0
mentioned earlier..
the answer is

Code: Select all

1
Similar I/O are given in the same thread try them out :wink:
If I will myself do hashing, then who will do coding !!!

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

Re: bipartite

Post by vinay » Sun Sep 03, 2006 5:00 pm

vinay wrote:By the way I would be blessed to get some useful links on Graphs, speciallly bipartite and its properties. Also some links for maximum matching algorithm... ohh the list is already too long.. :lol:

please someone forward it if possible :oops:
can anyone give some links please :cry:
If I will myself do hashing, then who will do coding !!!

hector-chang
New poster
Posts: 3
Joined: Sun Sep 03, 2006 4:14 pm

Re: correct algo

Post by hector-chang » Sun Sep 03, 2006 5:09 pm

vinay wrote:The algo is correct...
for each connected component find the minimum no. of guards...
return the sum of all guards of all components...

Check this I/O :

Code: Select all

1
1 0
mentioned earlier..
the answer is

Code: Select all

1
Similar I/O are given in the same thread try them out :wink:
Thanks. But the output is correct, it gives me 1

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun Sep 03, 2006 7:31 pm

Try this Input
Input

Code: Select all

1
5 1
3 4
Output

Code: Select all

4
Thanks
MAP

hector-chang
New poster
Posts: 3
Joined: Sun Sep 03, 2006 4:14 pm

Post by hector-chang » Sun Sep 03, 2006 7:39 pm

Also correct.

Thanks

ivan.cu
New poster
Posts: 21
Joined: Sun Mar 19, 2006 7:50 pm
Location: Cuba

Re: Some test cases!

Post by ivan.cu » Mon Sep 04, 2006 12:50 am

Help please!!!

Some one can give me test cases such not work for the following greedy algorithm:

Code: Select all

1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.

if exist unvisited street print -1
else print guards
Thank in advance

ivan

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: Some test cases!

Post by sclo » Mon Sep 04, 2006 1:39 am

ivan.cu wrote:Help please!!!

Some one can give me test cases such not work for the following greedy algorithm:

Code: Select all

1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.

if exist unvisited street print -1
else print guards
Thank in advance

ivan
It fails for certain types of graphs that are almost regular, because on some graphs, more than one node will have max degree.
consider this:

Code: Select all

10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 0
Probably your algorithm will visit 0 first, then delete edges, but there are now many nodes with max degree 2, you don't know which one to pick.
If you pick any odd numbered nodes, your algorithm will output wrong answer. The way to fix it is to fix your step 4. Instead of picking any node with largest degree to visit, why don't you just put a guard on a unvisited node adjacent to a neighbor of the node where you have already put a guard.

bafu
New poster
Posts: 2
Joined: Sat Jul 10, 2004 5:49 pm
Location: Taiwan

Post by bafu » Mon Sep 04, 2006 2:28 am

Dear ivan, here is the example which will prove the greedy algorithm is wrong:

Code: Select all

input:
1
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:
4
If you use the greedy algorithm, the output will be 9

ivan.cu
New poster
Posts: 21
Joined: Sun Mar 19, 2006 7:50 pm
Location: Cuba

Thank!!

Post by ivan.cu » Mon Sep 04, 2006 5:01 am

Thank, i can see now that greedy no solve it.

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

Re: bipartite

Post by Martin Macko » Thu Sep 07, 2006 2:06 pm

vinay wrote:
vinay wrote:By the way I would be blessed to get some useful links on Graphs, speciallly bipartite and its properties. Also some links for maximum matching algorithm... ohh the list is already too long.. :lol:

please someone forward it if possible :oops:
can anyone give some links please :cry:
You can google it yourself... try to start with http://www.google.com/search?q=bipartit ... algorithms.

Post Reply

Return to “Volume 110 (11000-11099)”