Блог пользователя snuke

SRM637 Div1Medium
Автор snuke, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hmm, nice.

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← 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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.)

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить