Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

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

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
  • Проголосовать: не нравится

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

Hmm, nice.

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

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

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

→ Ответить