PROBLEM LINK:
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 
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.