### snuke's blog

By snuke, 7 years ago,

SRM637 Div1Medium can be solved even if the width of the board is very very large.

There is O(|black cells|) solution.

Let's consider only 8 cells near the edge. There are three(four) cases:

1) There are black cells in both side.

In this case, already result is fixed because the players can not change a parity of the number of turns while the game ends.

2) There are black cells in only one side.

In this case, the first player can win because he can decide a parity by coloring the other side cell black.

3) There is no black cell in both side.

In this case, the player who color a side cell black at the first loses. Hence the winner in the board without 8 side cells wins. You can determine the winner recursively.

0) The width of the board is less than 4.
In this case, it is easy to determine the winner.

• +48

 » 7 years ago, # |   0 Hmm, nice.I'm curious: what was the reason for the initial systest fail?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 My first solution contained a bug and I fixed but it was not updated in the system for some reason. Sorry for that.
•  » » » 7 years ago, # ^ |   +5 I know what you mean, MPSQAS does some weird shit sometimes. I used to save by "save statement -> submit -> save statement -> submit".
•  » » » 7 years ago, # ^ |   0 Did your buggy solution fail on test case {".", "."}?
•  » » » » 7 years ago, # ^ |   0 No. It was a strange bug so I think nobody took the same mistake with me.
 » 7 years ago, # |   0 Strictly speaking I think it's not (Black) anyway, because with the given input format you need to locate all black cells which takes O(Width) time anyway.
•  » » 7 years ago, # ^ |   0 If they want it to be the intended solution, I don't think changing the input format is impossible though.
•  » » 7 years ago, # ^ |   0 I didn't care the input format because it is not essential. (If the width of the board is very large, the input format will be changed.)
 » 7 years ago, # |   +16 Hmmmm, actually there is a more simple O(Blacks) solution for this problem, because of the nice pattern which can be seen in the computed grundy numbers. something like this:(Suppose we have black cells positions in a vector of integer pairs named v, sorted by their column numbers) int ans = v[0].X ^ (n - 1 - v.back().X); for (int i = 0; i < v.size() - 1; i++) ans ^= ((v[i + 1].X - v[i].X) % 2) ^ (v[i].Y == v[i + 1].Y); Second player wins if and only if ans equals zero at the end.