RANKA - Editorial

editorial
graph
jan15
medium-hard
ranka

#1

PROBLEM LINK:

Practice
Contest

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:
image
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:
image
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.
image
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

SOLUTIONS:

Setter’s solution
Tester’s solution


#2

If you visit this page, http://senseis.xmp.net/?LongestPossibleGame there are two algorithms listed.

The first algorithm is enough for Subtask 1, and the second algorithm can be used for both the subtasks.


#3

I would say this one is not “MEDIUM-HARD” it was just implementation heavy (especially for me converting from C++ to Java).

You can simply for each move find one empty field, put the stone there and check if this is valid move. If it is, do the same for next step (and save those in some list). If step is invalid, just return to previous step in list and place stone to next empty field and son on…

I’m sure that C++ guys can reuse a lot of code from judge.

My solution (in Java) was running a lot quicker on my machine than judge in C++ (I do not know why and I did’t event try to find out).

My strategy was to place stones for first player from upper left corner and from bottom right for second user…


#4

All I did was a dfs :slight_smile:
here


#5

I can’t understand some details of APPROACH2. If we’ll choose target cells in some other order, for example (1,1) - (1,3) - (1,5)… and then (1,2) - (1,4), than everything is ok. But how to make it work in order (1,1) - (1,2) - (1,3)? If we’ll try to do it strictly like in editorial, then at this step: player2 fills whole board except (1,2) (meanwhile player1 passes) player2 have to take white peg at (1,1), but he can’t take it without filling (1,2).


#6

Here’s the beginning of my approach: http://pastebin.com/g4GdiTG7 . Hopefully, you can extrapolate the pattern. I thought this strategy was nice since it was very short to explain (i.e. just define this recursively), and this generates over 400k moves.


#7

@lg5293: Oh, cool! If I know it is possible to make such many moves, I will make this problem into a challenge one (who makes most moves get 100 points, others get a fraction according their moves).


#8

In the editorial is mentioned Grey_code to generate moves … Is there any other other problem that makes use of it… I first time encountered the use of grey code in solution of a question…wanna know to explore its use in programming cometition other than its general use…:slight_smile:


#9

I definitely agree that it is not even MEDIUM-HARD. I am surprised that more people didn’t solve it.


#10

The peg at (1, 1) is already a second player’s peg. First of all first player fills the whole board except one cell, then second places a peg at the only free cell. After this move there is only one peg on the board (second player’s peg). After that second player adds 79 more his pegs and so on.


#11

I didn’t solve it because I do these contests for fun and I didn’t find this problem interesting. I guess a lot of people felt the same.