10561 - Treblecross

[subbu]

Can anyone post some ideas for this problem??

As far as i can see, we can compute whether a string of n '.'s is a
losing position or a winning position.

Once we know this information for n=1 to 200(200 is max '.'s as
described int the problem)...

we can scan the string and find out the number of w = winning positions
and the number of l = losing positions...

and check to see if w-l is odd or even outputting winning or losing.
respectively.

Ofcourse,finer details like checking whether there is a single move win
also can be dealt with...

Can anyone help me with outputting the moves for a winning position.??
and corrections and ideas shall be very helpful.

thx.

[BiK]

As far as i can see, we can compute whether a string of n '.'s is a
losing position or a winning position.

How do you compute this?

[marian]

This problem can be solved by Grundy-Sparague numbers theory. Just search the internet for Grundy numbers, or NIM-value to find the details.

[subbu]

to BiK:

I guess my ideas need refinement and corrections.
Any way this was wat i thought

Let us call a sequence of N '.'s
-------------------------------------------
| bounded on either side by an 'X' |
-------------------------------------------
a N-hole.

Ex:" X...X " is a 3-hole but "...X" is not.

Let us call an N-hole a winning position if Player1(the 1st mover)
wins the game assuming the board has a single N-hole;
A losing position otherwise.

Let there be a single N-hole in the board.

N = 1 ---> Player 1 wins.
N = 2 ---> Player 2 wins.
N = 3 ---> Player 2 wins.

For N>3 an N-hole is a winning position if and only if
there is an "I" such that (1<I<N-1)

I-hole as well as (N-I-1)-Hole are losing positions.

OR

I-hole as well as (N-I-1)-Hole are winning positions.

So,we can compute winning or losing positions for N = 1 to 200.

Now, we can see that (assuming there are only holes. in the board)
if there is no immediate winning position,
we can count W = no.of winning holes.
and L = no.of losing holes. and check if W-L is even(player 1 loses)
or odd(player 1 wins).

I suspect the validity of the above statement.
The above is purely on intuition.
So, any proofs or counter examples are welcome.

But thats how far I came.
I realised that there need not be just holes on the board.
I dint get the time to think of something about
"holes" not bounded by "X' on either side.

If u didnot understand, do ask me.
I am looking for suggestions and Corrections to the above
line of thinking.

2 Marian:
Thx for the help.
I am going to look it up now.

[BiK]

For N>3 an N-hole is a winning position if and only if
there is an "I" such that (1<I<N-1)

I-hole as well as (N-I-1)-Hole are losing positions.

OR

I-hole as well as (N-I-1)-Hole are winning positions.

So,we can compute winning or losing positions for N = 1 to 200.

The above statement is incorrect. Consider the following counterexample (a 14-block):

[cpp]X . . . . . . . . . . . . . . X[/cpp]

And the first player plays like this:

[cpp]X . . . . . X . . . . . . . . X[/cpp]

Now the two 5 and 8 blocks are winning positions (you can check this easily) and according to you the initial 14-block is also a winning position. When I read your first message I tried to compute the winning and losing positions the same way. However I found the flow in this method and that's why I asked you about your method. Now I describe the flow:

The problem is that you describe the positions as winning or losing. That is incorrect. The positions can be:

1. Losing - there is no way to win

XOR

2. Winning/Losing - there is a way to win but of course there is a way to lose.

Now let's go back to the counterexample. We actually have two Winning/Losing positions. The second player is not obliged to play the winning move for the 8-block. Instead he plays a losing move for the 8-block as follows:

[cpp]X . . . . . X . . . . . X . . X[/cpp]

Only for the 8-block this was a losing move. But for this game it was a winning one. You can continue playing and see that the first player loses though you claim the opposite.

However once I figured out this I couldn't repair the method. Now I turn the ball back to you. Could you suggest how to bring this idea to an end?

[BiK]

2marian:

I tried searching for a Nim-value but I couldn't find anything usefull. Could you explain the algorithm (I liked your explanation of 10574 Counting Rectangles very much) or could you point out some usefull reference on the subject.

[marian]

Well, this stuff is a bit complicated, involving a lot of math. With this kind of problems there is an interesting story. I was participant of CEOI 2000, where was very similiar problem (http://ceoi.ubbcluj.ro/internet/p5.html). This problem can be easily and efficiently solved by Grundy numbers. Participants from my country knew it, because we have trained Grundy numbers on our local contests. Problemsetters probably didn't know this theory, so the sample solution was something like backtrack. That's why we've wondered, why the input is so small, when we can solve quickly a lot larger inputs.

So a rough idea for this problem: Firstly, we check, whether there are two X in a row. Winning moves in such position are clear. So assume, that input looks like this: a_1 dots, X, a_2 dots, X, ... X, a_n dots. We divide this game to n independent games.

First thing to consider is that position: X a_i dots X is the same as position: a_i-4 dots assuming that both players play perfectly. This is because one can't make X in first two or last two dots, because the other player will win easily. (similiar for positions a_i dots, X and X, a_i dots (X only on one of the sides) These are equivalent to a_i-2 dots) So the initial position turns out to be n independent positions with a_1-2, a_2-4 ... ,a_{n-1}-4, a_n-2 dots.

For every position we compute nonnegative integer called Grundy number. Grundy number equals zero iff the position is losing. Grundy number for the position P is the minimum number x such that we can't get from P to position with Grundy number x.

Grundy number of a position, which is a set of independent positions is XOR of grundy numbers of that independent positions.

If we have position with k dots, to which positions we can get? Consider we put X on i-th dot. We will get position: (i-1) dots, X, (k-i) dots. We know that this is equivalent to 2 independent positions: first is (i-3) dots, second is (k-i-2) dots. If g1 is grundy number for first position and g2 is grundy number for second position then grundy number of these 2 indepedent positions is g1 XOR g2. So from position with k-dots, we can get to position with grundy number g1 XOR g2. We compute this for every i and we get grundy numbers of all positions, we can get to. Minimum value not in this list is a grundy number for the position with k-dots.

Position with zero (or less ) dots has grundy number zero. (because it is losing) So now we can compute grundy number for every position with k-dots.

So return to initial position. It is n independent positions with a_1-2, a_2-4 ..., a_n-2 dots. Let G(i) be the grundy number for position with i-dots, then grundy number for initial position is G(a_1-2) XOR G(a_2-4) XOR ... XOR G(a_n-2). If this number is zero, initial position is losing. If is it positive, it is winning position. How to find all winning moves? That's simple, try all possible moves, and the one, that will give the resulting position with grundy number zero is winning move.

Why is it true? Well this is where that 'a lot of math' comes But don't want me to explain it in this post

[BiK]

Wow! Where have you been till now. You're great! Thanks a lot man. Be sure that when I have free time I'll read the math behind all this.

Some implementation questions:

1./How are these grundy numbers distributed? How big can they be?

2./Assuming that the grundy number for positions with zero or less dots is 0, I manually computed the grundy numbers for positions with 1 and 2 dots (these positions are boundary). These grundy numbers are 1. Am I right?

3./What if the board position begins with an X? Then I try to compute the grundy number for -2 (because as you said I try to jump over 2 points to the left) which is 0. Am I right?

4./When I walk through the independent positions of the board I have to accumulate their nim value, that is I have to do something like this

[cpp]g = g xor Grundy(current independent position)[/cpp]

How do I initialize g?

Best regards.

[marian]

Some implementation questions:

1./How are these grundy numbers distributed? How big can they be?

Well the worst case is, when we can get to all previous positions from given position. So when we have G(0)=0 and for every i we can get to all positions <i (they have grundy numbers {G(0),G(1),...,G(i-1)}={0,1,..,i-1}, then G(i)=i. This was the worst case, so G(i)<=i.

2./Assuming that the grundy number for positions with zero or less dots is 0, I manually computed the grundy numbers for positions with 1 and 2 dots (these positions are boundary). These grundy numbers are 1. Am I right?

You are right. Grundy number for 3 dots is 1, too. For 4 dots it is 2, because we can get to position 1 (when we put X to edge dots) and 0 (when we put X to any non-edge dot)

3./What if the board position begins with an X? Then I try to compute the grundy number for -2 (because as you said I try to jump over 2 points to the left) which is 0. Am I right?

Yes. You can imagine that trick with -2 or -4 like you are making some "forbidden area" of size 4 around every X. When you have ....X.... then forbidden area is ..xxXxx.., because if is foolish to put X there. When the situation is .X... then the forbidden area is (x)xXxx..., but the first 'x' is "out of range" so it is clear that we can't put X there.

4./When I walk through the independent positions of the board I have to accumulate their nim value, that is I have to do something like this

[cpp]g = g xor Grundy(current independent position)[/cpp]

How do I initialize g?

You can initialize to 0, because 0 xor G = G for every G.

[BiK]

Thanks again man. I solved the problem. Your help was priceless.

I know that probably I ask too much but problem 10571 Products is just another intractable for me problem and I wonder whether you have succeeded to solve it. If so could you help me with it?

Best regards.

[subbu]

2 bik:

Thx for the example.
The positions can only be classifid as losing or can't say.
and the exact outcomes seem to be dependent on th grundy numbers
as *explained* by marian.

2 MARIAN:

Thk you so much man..

for introducing me to the fascinating world of gametheory.

[hamburger]

10561--- Please give me some INPUT. Thank you.
I got WA many times.

[hamburger]

my input is:
23
.....
X.....X..X.............X....X..X
.X.X...X
...............................................
.X.X.X.................X...X.............X......
X...........X.....X......X...................X.....
.....X...........XX......
.........
.X.XX...
.......X
...........XX
.X..........XX
XX..........XX
.X.......X......
X................X.
X.......X........X....X...X
.....................
.............
...................................
............XX..........
.........X.......................................X......
.......................X......X.................X.......
.X..............X.................X..........

my programme's output:

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
3 8 19 21 22 46
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
7 12 13 15
LOSING

WINNING
12 15
WINNING
11
WINNING
7
WINNING
1 3 7 8 17 18 19 28 29 33 35
WINNING
12 15
LOSING

WINNING
36 37 41
WINNING
18 20 21 28 29 31 32


Who can tell me is that right? Thx!

[hamburger]

Help Me!

[dapumptu]

Can you tell me what method do you use to solve this problem?????