KNICOV - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

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

3 Likes
2

@deadwing97 Could you please upload your solution?

3

I get the things @deadwing97 is trying to put across. But i have 2 queries.

So our answer for N = 2 equals :

⌊M6⌋∗4+min(M mod 6,2)∗2

I want to know, how did you reach here from the observation that knights should be fitted in middle for N=2?? And after getting, how did you verify that “Yes, it IS the minimum.” ??

My second query is, like, how to think when we get these type of questions?

I tried a brute force solution, by making a N x M boolean matrix. Places where knight are placed or can attack are marked 1, rest 0. But this method failed because “Where do you start placing, such that knights are minimum?”

Is it possible that this Q could have a similar brute force algorithm, where after iterating over the entire matrix for ‘K’ (a constant) number of times gives us the answer?

4

@vijju123 I have answer to your first query , see
Case 1:

We know that if number of columns are a multiple of 6 then
GIf(M/6)*4 are the minimum number of knights (because putting knights in the middle is always efficient than at corners so that they attack both directions)
Case 2:

If they are not multiple of 6 that means that at least 5 columns are unfilled or say untouched by any of the knights(assuming that i fill the number of columns which are divisible by 6 in similar way Case 1).
But the remaining columns need to be filled so for that min(M mod 6,2)*2 is the answer because M mod 6 shows the columns not attacked yet(columns less than 6) ,so if say column is one then we need two knights (for two rows and one column), otherwise we need only two columns and 4 knights .

You can draw it on paper for all columns less than 6 and row 2 , it is easy to see why it is 4 knights.

1 Like
5

I didn’t get your second query properly but i guess answer to “Is it possible that this Q could have a similar brute force algorithm, where after iterating over the entire matrix for ‘K’ (a constant) number of times gives us the answer?” is no because we have to decide the positions of knights on the matrix first and this solution gave a pattern so "iterating over the entire matrix " may not be the solution. Again, I am not sure its just from what i understood about this question till now

Hope it helps:)

1 Like
6

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.

That’s how you can come up with the observation for N = 2

As for the DP solution, to be honest I am familiar with problems alike. Don’t get frustrated :slight_smile: It’s not something really easy to get yourself without past experience

1 Like
7

@deadwing97, Can you please upload a solution with comments in it? The tester’s solution is quite hard to understand for me on how he updated the dp.

8

Actually it’s my code, and I believe it’s kind of clear as you understand what is written. I try all possible choices of the new column’s mask and the function make updates the attacked cells for the current 3 columns and also keeps the attacked cells from previous columns.

9

Bonus: Find the O(1) solution for n=3

2 Likes
10

@alei , I could figure out the O(1) pattern for n=3 by running one of the DP solution from the contest against few test case, its same as for n=2 the only difference is that for m>12, if m%6==2 then the knight count will be (m/6)*4 +3 but I couldn’t get the configuration of knights on the grid for which this solution is working. It would be great if you could help me finding that configuration. Thanks in advance.
My solution for this pattern: https://www.codechef.com/viewsolution/14297214

11

n=3, m=14

..**.* .. ..**..
..**.. .. ..**..
...... .* *.....
1 Like
12

My solution to this problem… Like Editorial Dp solution…


I think it is understandable