PROBLEM LINK:
Author: Gaoyuan Chen
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM-HARD
PRE-REQUISITES:
Ad-hoc, Graph theory, Games
PROBLEM:
Given a empty board of 9x9, each of the two players(black and white) move alternately. In each move, the player must put the stone on an empty cell or pass the turn. If this player put a stone, following situation will happen.
-> If after this move there is at least one connected component of opponent dead, then stones from these dead components will be removed. (In this case, after remove all dead components of your opponent, we can prove all your connected component are not dead.)
->Otherwise, if there are at least one connected component of yours dead, then this move is invalid.
In order to avoid infinite loops, there is a rule called “No same state”. The state of board can be expressed as a string with length 82:
the first character indicate who is the next player, then 9*9 character indicate the state of a certain cell. If after one move the game goes into a state that previously occurred, then this move is invalid.
Player can also use to “pass” their move(ie. no change in state).
You are given an integer N. Please output a match that contains N valid moves for both player.
EXPLANATION:
There can be many solutions to this problem. You can think of various game plays where connected components get deleted(while making sure the state remains unique). One or two of them, I’ll explain here.
->I request users to explain their approach if it’s unique/different. It surely will help others.
APPROACH 1:
1. The Gadget: Ko
We will use the following gadget to build our answer:
It has the following feature: the left state can transform into the right state by place a white stone, and the right state can transform back into the left state by place a black stone.
This structure in Go is called Ko: http://en.wikipedia.org/wiki/Ko_fight
2. How to use Gadget
We can place lots of this kind of gadget on the board, for example, this configuration has 8:
So one state can be represented by an 8 bits number: 0 to 255. We want to go through these 256 numbers, the adjacent ones should have at most 1 bit different. How to do that? We can use Gray code: http://en.wikipedia.org/wiki/Gray_code
So we can make about 256 * 1.5 steps now. (if we place want to place 2 black(white) stone in a row, we
must pass one turn, so on average it needs 1.5 moves for one number).
3. Use the remaining cells
After each 256 * 1.5 steps, we can modify the remaining board a bit, then make another 256 * 1.5 steps
and so on. We can just fill in one cells each time: the cells that marked with a red circles.
Now we can generate answer for about 256 * 1.5 * 30 moves, that is enough.
APPROACH2:
The basic thinking behind this approach was behind the fact that if player1 passes each time and player2 fills up the whole board(cell by cell) except one cell, player1 can now, place in the empty cell and remove all pegs of player2.
In such a way, players can keep leaving one cell empty(different cell each time). So, we can generate a total of 81*81*2(note the passes).
Note all states generated are unique.
So, following moves will be generated:
player1 fills whole board except (1,1) (meanwhile player2 passes)
player2 puts at (1,1) (all pegs of player1 get removed)
player2 fills whole board except (1,2) (meanwhile player1 passes)
player1 puts at (1,2) (all pegs of player2 get removed)
player1 fills whole board except (1,3) (meanwhile player2 passes)
player2 puts at (1,3) (all pegs of player1 get removed)
.
.
.
and so on for 81 cells.
APPROACH3:
Use some strategy to search for an answer directly: http://www.codechef.com/viewsolution/5731906
