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?
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.
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
Im not familiar to bitmask DP… Do you have any good link where it is explained?
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:
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??
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?
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.
is it possible to solve this question using maxflow aur min cut??
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.
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
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.....
Thanks @hikarico
Sample for solving N=3 and M=14 case.
EEKKEK EEEEKKKK
EEKKEE EEEEEEEE
EEEEEE EKKEEEEE
Perfect, thank you.
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
Finally found a good tutorial on bitmask dp, try this