KNIGHT COVERING - june cook off 2017

Can anyone explain how to solve the problem KNICOV from june cook off…I saw some solutions that DP and bitmasking but was unable to understand.
Question Link -> contest practice

We need to cover a n x m chess board. To do this, let’s assume we have some information on the first m-1 columns. We can assume that the first m-3 columns are already covered since nothing we put in column m can possibly affect them. We need to keep track of where the knights are in columns m-1 and m-2, as well as which squares in those columns are already covered by some knight in the first m-3 columns. So the state space is (number of columns, state of column m-1, state of column m-2). Each cell in the last 2 columns can have 3 states: already covered, filled with a knight, uncovered and empty. So there are m * 3^(2n) states in total. Each state influences 3^n successor states because there are 3^n ways to fill the next column, which gives us a m*3^(3n) algorithm. But you can do all this locally on your computer, notice a pattern, and submit a way simpler program because the pattern repeats after a while. That is, for n=2 and n=3, we have f(n,m) = f(n,m-6) + 4 for large enough m.

1 Like

is it possible to solve this question using max flow or min cut??