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