KNICOV June cook off

general
,
1

Hello… I tried to solve KNICOV problem in June Cook off and I could not figure out for cases like N = 3 and M = 10. Did somebody managed to find a pattern in the position of the Knights?

1 Like
2

At least for me I wasn’t able to find any good pattern. The answers are weird for skipping periods of 6 and 7. The safe way to solve this problem is to do bitmask DP that relates a row to a mask of its two previous rows.

3

There is a good pattern there, but edge cases are too risky.

    N=1, ans=M
    N=2, 
    ans=(M/6)*4+4;
    if(m%6==1) ans-=2;
    if(m%6==0) ans-=4;

for N=3, this pattern continues till M=13.
From then whenever M%6==2, ans would be +3 instead of +4.

Here’s a link to my answer. Comment if you have any doubts

3 Likes
4

Im not familiar to bitmask DP… Do you have any good link where it is explained?

5

Update, I found a pattern for 2 \leq N \leq 3. Haven’t proven yet if it works for big N, but for now it looks like this:

f(2, m) = 4\lceil \frac{m}{6} \rceil - 2\times max\{0,1 - ((m-1) \mod 6)\}
f(3, m) = \begin{cases} 3 & m=1 \\ f(2, m) & 1 < m \leq 8 \\ 4\lceil \frac{m}{6} \rceil - max\{0,2 - ((m-1) \mod 6)\} & 8 < m \\ \end{cases}
6

Can you show that sample of N=3 and M=14? I used a similar pattern for N=2 and N=3; can´t figure out a different pattern (perhaps because i was looking for cases until M=14).

This is the pattern i used for N = 3:

EEKKEE EEKKEE EEKKEE …

EEKKEE EEKKEE EEKKEE …

EEEEEE EEEEEE EEEEEE …

Each new block use 4 Knights for covering the whole block; except when M%6 = 1, where two Knights are enough (placing one on previous block):

EEKKEE EEKKEE E

EEKKEE EEKKKE K

EEEEEE EEEEEE E

I guess that should be a way for covering a block of 3 * 8 using only 7 Knights, seems to be logic now :slight_smile:

7

Can anyone comment if this Q could be done via brute force?? Since board is small, Make a boolean array of 0 and 1. If arr[i][j]==0, then place a knight at a cell and mark the cells 1 where it can attack and where its positioned.
Any comments??

8

I went down the pattern path, but was unable to identify the pattern when n == 3 and m > 13 and m % 6 == 2, as described in the accepted answer. However, even after reading that, I still can’t find a way to place 11 knights to cover a 3 x 14 board… Can somebody show me?

i.e. I can’t figure out how to deal with these question marks with only three knights:

..KK.. ..KK.. ??
..KK.. ..KK.. ??
...... ...... ??

Can you share a potential solution that uses 11 knights to solve 3 x 14?

9

I feel finding the pattern for m - 14 was too much for me.
So, I ended up getting a wrong answer (cause I found till m = 6 -_-). Is there anyone who used backtracking or other method to solve the problem ? It might be slower but it will take care of all the corner and edgy cases.

10

Here’s some configurations for N=14 with 11 knights:

..KK.K....KKK.
..KK.......K..
.......KK.....

..KK.K....KK.K
..KK..........
.......KK....K

..KK.K....KKKK
..KK..........
.......KK.....
2 Likes
11

Thanks @hikarico

Sample for solving N=3 and M=14 case.

EEKKEK EEEEKKKK

EEKKEE EEEEEEEE

EEEEEE EKKEEEEE

1 Like
12

Perfect, thank you.

13

@hikarico Can you explain the DP solution?

14

is it possible to solve this question using maxflow aur min cut??

15

Fix a column. If I place knight, it will affect upto two columns to the left. If n=3 there are six slots to the left, you can do DP with 2^6 states for the knights, and another 2^6 for the missing positions. Total is 2^{12} m states which is enough to solve the problem.

You can also reduce it to 3^6m states by making it ternary, but thats not needed :slight_smile:

16

can a knight only attack one other box other than the one it is placed on?

because if that’s not the case then we can easily solve this problem using only 4 knights for n=2, isn’t it? Please help me out here.

17

Finally found a good tutorial on bitmask dp, try this

http://codeforces.com/blog/entry/45223