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.
is it possible to solve this question using max flow or min cut??