### PROBLEM LINK:

**Author:** Alei Reyes

**Primary Tester:** Hussain Kara Fallah

**Secondary Tester:** Kacper Walentynowicz

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy - Medium

### PREREQUISITES:

DP , bitmasks

### PROBLEM:

Given a board consisting of **N** rows , **M** columns. **(N <= 3 , M <= 50)**. What is the minimum number of knights we could place such that each cell is occupied by a knight or attacked by at least one knight.

### OBSERVATIONS

Let’s consider some cases first:

If **N = 1** ,then it’s clear that we should fill our board completely, because a knight cannot attack a cell in the same row. So we must fill all of them.

If **N = 2** , let’s consider the starting few cases

**M=1 or M=2** we should completely fill the board

**M = 3** we should fill it this way

Empty | Knight | Knight |

Empty | Knight | Knight |

**M = 4** try to figure it yourself.

Let’s consider **M = 6**, the optimal way to fill for **N=2,M=6** is :

Empty | Empty | Knight | Knight | Empty | Empty |

Empty | Empty | Knight | Knight | Empty | Empty |

It’s optimal to place our knights in the middle because a knight can attack cells to the left and to the right. You can notice that this is strategy is optimal for filling boards consisting of **2** rows and any number of columns. Taking each **6** consecutive columns and placing 4 knights in the same way above. Because to eliminate the first column you must place 2 knights either in the first column or in the third column, and of course placing them in the third is better (so they can eliminate another succeeding columns). The same relation holds between the second and the forth column. You can prove the correctness by this logic and continue filling the board.

So our answer for **N = 2** equals :

\lfloor{\frac{M}{6}}\rfloor * 4 + min(M \ mod \ 6 , 2) * 2

Now we are left with **N = 3** case, this is solved by Dynamic Programming.

### EXPLANATION:

First of all let’s think of a recursive solution to fill the board and pick the cheapest way. Something important we should take advantage of is that we have only **3** rows, so filling the board column by column would make it much easier for us. So let’s fill them one by one from left to right:

Let’s say we are filling a certain column, which columns affect our current? The next 2 columns may affect our current one (but we will take them down later since we are filling from left to right), and the previous 2 columns. Also, our current column affects the next 2 and the previous 2. So it’s mandatory to know the knights placement configuration in the previous 2. Columns further than 2 steps don’t affect our current column. We can store information about each column in a mask of 3 bits.

So is it enough to store only information about the knights placement in the previous 2 columns?

Actually No, Let’s consider the pre-previous column (the one before the previous). It may contain some **empty** cells which are attacked by columns behind it (and we don’t have information about them since we are only keeping info about the last 2). After filling our current column we should get rid of the pre-previous column before continuing to our next one, so we must assure that cells of this column are all attacked (so we are missing some information that we must have kept in order to determine that the pre-previous column is completely attacked). This information can be kept in different ways. In my solution, I store information about the attacked cells in the previous 2 columns in addition to knights placement in them and update this information between calls of my function. By attacked cells I mean for each column, I mark cells which are occupied or attacked by any other previously placed knight.

This information is enough to make us able to write a Dynamic Programming solution:

**Dp[column][PrePreAttacked][PreAttacked][PrePreKnights][PreKnights]**

For each state, we should iterate on all possible ways of filling this new column, after that we must make sure that Pre-Previous column cells are all attacked (after filling our current column in addition to information we have about it).

After that we can take rid of PrePrevious column and proceed to the next column. Of course we should update the information about the attacked cells in the Previous column (which will be the pre-previous column after we call the function for the next one) and also update the attacked cells in our latest filled column (which would become the previous) before calling the function for the next column.

Another Dynamic Programming solution is done by keeping information about knights placement in the previous 4 columns.

This solution runs in :

**O(M * 2^ ^{5*n})**

Final Note:

This DP solution works for all N (small values because complexity is pretty huge), but I found that solving N={1,2} cases separately would make it easier for me while implementing the DP.

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Will be uploaded soon.

**TESTER’s solution**: [Here] 555