11080 - Place the Guards

[ivan.cu]

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]

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

[vinay]

me too... Thanks to martin and kp...

[vinay]

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

[hector-chang]

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]

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

[vinay]

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

can anyone give some links please

[hector-chang]

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

Thanks. But the output is correct, it gives me 1

[mohiul alam prince]

Try this Input
Input

Code: Select all

1
5 1
3 4

Output

Code: Select all

4

Thanks
MAP

[hector-chang]

Also correct.

Thanks

[ivan.cu]

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]

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]

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]

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

[Martin Macko]

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

can anyone give some links please

You can google it yourself... try to start with http://www.google.com/search?q=bipartit ... algorithms.