Kallaf's blog

bfs problem
By Kallaf, history, 6 years ago, In English

bfs problem: https://codeforces.net/problemset/problem/1105/D

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

Comments Comments (4)
| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

And what?

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

I think the best way of getting some idea about a problem's solution is looking at the editorial. Here's the Round 533 (Div. 2) editorial: https://codeforces.net/blog/entry/64664

It's a simulation problem so your task is only to simulate the game following a given set of rules. They're unequivocal so for a particular initial grid, there's only one correct course of the game. The algorithm that you need is multi-source BFS. Firstly, put on the queue all of the cells which belong to some player. Then, simulate the turn as below: Take one player (which is first in order) and using BFS, expand his cells. Then, take the next player... finish it when there are no empty cells left.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

If you put on all cells, which belong to some player, in the queue, I'm not sure that it is a clear O(n^2), because every move you traverse over all visited cells. And if the moves are a lot (a sample can be constructed) the complexity can possibly reach O(n^3). One possible optimization is to put only cells, which were end points on the previous move. It's pretty obvious that the other cells are useless and you can observe that this way we visit every cell at most twice, which leads to a clear O(n^2) solution. The most solutions passed without this, but in my opinion the test cases are pretty weak.

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

    Of course, that's what I meant. We put all cells which belong to some player only in the first move. Then, only these which are 'new'. Like in normal BFS. Thanks for clarification because I didn't say it plainly. Really, did solutions O(n^3) passed? So the test cases were really weak.

    → Reply