## 11080 - Place the Guards

Moderator: Board moderators

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

### Some test cases!

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

ivan

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
Thanks for sclo and Martin Macko, I got AC at last !!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
me too... Thanks to martin and kp...
If I will myself do hashing, then who will do coding !!!

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

### bipartite

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

please someone forward it if possible
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

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

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

### correct algo

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

Code: Select all

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

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

### Re: bipartite

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

please someone forward it if possible
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

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

Code: Select all

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

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
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
Also correct.

Thanks

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

### Re: Some test cases!

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

ivan

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

### Re: Some test cases!

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

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

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

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

### Re: bipartite

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

please someone forward it if possible