MACGUN-Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Medium

PREREQUISITES:

Graph theory, Bipartite graphs, Maximum Matching

PROBLEM:

You’re given an N * M grid. Some cells of the grid have a gun, some other have a
protector and others are empty. Two guns A and B can attack each other if both x
and y cordinates of A and B differ by exactly two units, however they’re
shielded if there is a protector between them. You’ve to find out how many more
guns can be added to the grid such that no two guns attack each other.

QUICK EXPLANATION:

Create a graph where cells are vertices. Put an edge between two vertices if
they can attack each other. This is bipartite graph and we need to find out the
size of largest independent set which can be found using Koneig’s theorem. We
just need to find out the size of maximum matching.

DETAILED EXPLANATION:

It is actually a fairly standard graph theory problem.

Let’s create a graph where each cell of the grid is a vertex. Some of these
vertices already have a gun / protector on them. Remove these vertices from the
graph. There are some other vertices which are currently empty but
on which one can’t place a gun because of the guns already placed in the grid.
Remove these vertices from the graph as well.

Now we’ve a graph where every vertex is currently empty and a gun can be placed
onto it. We’ve not decided the edge set of the graph yet! So let’s say there is
an edge between two vertices if guns placed on the corresponding cells of the
grid could attack each other.

Now we need to choose some of these vertices and put guns on them. Constraints
of problem tell us that we can’t choose two vertices which have an edge between
them. So the set of vertices we choose must be an independent set. Moreover, as
problem asks us to place the largest possible number of guns, we need to find
the largest possible independent set.

Now finding out largest independent set in a general graph is NP complete. So
there must be some structure to this graph that we’re missing. Actually if you
look more carefully, this graph is a bipartite graph. One of the possible
partitions is as follows :

Call all those cells as left side which are in (4k+1 and 4k+2) columns and call
remaining cells as right side. It is easy to see that this is a valid
bipartition - there is no edge between vertices of the same side.

Now we’ve a bipartite graph and we need to find the size of the largest
independent set in this graph. By Koneig’s theorem, size of the largest
independent set is equal to the size of the largest matching in the graph.
Maximum matching can be found be using any matching/flow algorithm. In
particular, as the graph size is huge, we would need a fast matching algorithm.
You could take a look at the setter solution for Hopcroft Karp algorithm.

There is an optimisation that one could do - notice that the graph is
disconnected. Classify the points on the basis of parity of their x and y
cordinates. Four different classes are (even, even), (even, odd), (odd, even)
and (odd, odd). These are four disconnections of the graph and each of these is
bipartite. So you could as well solve each of these seperately. This would save
both some memory and time for you.

Bonus problem : What would be the solution if we’re also allowed to place
protectors on the empty cells? I don’t have a solution for it yet. If you do,
please share it here :slight_smile:

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

1 Like

In fact, there are eight independent components defined by the values of ((x + y) 4, (x - y) 4).

6 Likes

Lets take point (0,0) and (2,0). First point is from (0,0)-th Component, second one - from (2,2)-th Component. They belong to different components, but they have and edge between them. Guess, you wanted to say “… defined by the values of ((x + y) 2, (x - y) 2)”, unless you are mistaken.

Points (0,0) and (2,0) are not connected by an edge.

2 Likes

I try to solve it with Kuhn, but get TL. Is this mean I must use Hopcroft-Karp algorithm, or it’s just my bad implementation?

Moreover, in Wiki I founded

The size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.

but you say

By Koneig’s theorem, size of the largest independent set is equal to the size of the largest matching in the graph.

Where I’m wrong?

Thanks.

1 Like

0
I try to solve it with Kuhn, but get TL. Is this mean I must use Hopcroft-Karp algorithm, or it’s just my bad implementation?

Moreover, in Wiki I founded

The size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.

but you say

By Koneig’s theorem, size of the largest independent set is equal to the size of the largest matching in the graph.

Where I’m wrong?

Thanks.

Today I’ve fixed some of my bugs, and tried to resubmit source.
I read that Dinic work on bipartite graph near Hopcroft-Carp algorithm. I wrote it, and on my PC on max test it works about 3 seconds. But I still got TL. What’s wrong? Can you help me?
My solution : http://www.codechef.com/viewsolution/1274631

if we consider every connected component of the graph individually. This component has the property -

  1. bipartite
  2. planar
  3. max degree of any node is 4
    Intuitively I feel that the maximum matching/ MIS for this graph should be one of the two set themselves. I am not able to prove this or find a counterexample. Where am I going wrong?

I managed to do it with Kuhn’s algorithm (O(VE)).

But it required some optimizing. 3 changes I did, but probably the 3th was the biggest win for me.

  1. As in editorial, there are 8 independent graphs. So run the algorithm on all 8 seperatly.
  2. The algorithm how I knew it created a new boolean array that holds which nodes are already visited. This consumes a lot of memory, instead hold in which iteration it was visited the latest and check if the last iteration is equal. So only 1 array should be created over all iterations.
  3. The algorithm checks if the vertex on the right side is already taken and if so, it is going to do dfs on that. Instead I first checked if there was any other vertex untaken. So the algorithm was more likely to break faster.

Sol in java:
https://www.codechef.com/viewsolution/13351619