snuke's blog

SRM637 Div1Medium
By snuke, 10 years ago, In English

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.
fig2
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.
fig1
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.
fig0
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.

  • Vote: I like it
  • +48
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hmm, nice.

I'm curious: what was the reason for the initial systest fail?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    My first solution contained a bug and I fixed but it was not updated in the system for some reason. Sorry for that.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I know what you mean, MPSQAS does some weird shit sometimes. I used to save by "save statement -> submit -> save statement -> submit".

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did your buggy solution fail on test case {".", "."}?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No. It was a strange bug so I think nobody took the same mistake with me.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If they want it to be the intended solution, I don't think changing the input format is impossible though.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.)

    → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply