10838 - The Pawn Chess

[Dreamer#1]

Are there any special cases in this problem? I can't find any! a plain solution should have taken care of everything but unfortunately I'm getting WA.

Can someone please verify the following cases:

Code: Select all

Input:

8

....
..p.
pp..
P.P.

p.pp
....
P...
P...

.pp.
....
....
.P..

.pp.
...p
..P.
...P

..p.
.pPp
....
...P


pppp
....
....
PPPP

..p.
....
...P
P...

....
....
.p..
P...


Output:

black (4)
black (4)
black (2)
black (4)
black (2)
white (11)
white (3)
white (1)

If the above are ok then can someone please give cases that might be more tricky.

Thanks in advance.

[stubbscroll]

Your output is correct. I don't think there are any special cases, the only potential special case I could think of is not legal (black already won, "black (0)"). If you didn't hardcode your program to 4 pawns or less, you might want to try this (also illegal input):

Code: Select all

1

pppp
pppp
PPPP
PPPP

Output: white (15)

[SilentStrike]

I had a bug because I was trying to encode the states into a 32 bit integer, and there was some problems in storing the pawn in the bottom right (most signficant two bits in my integer). If you are encoding into an int, try using 64 bits for safety.

[Dreamer#1]

Thanks... Got AC.
But I need to stop listening to music while coding.

[jagadish]

Can someone tell me how to optimize this program genuinely ? i used some cached values to pass the test data(1.84 sec )..a few of them have got less than 0.01s

[SilentStrike]

Was it a 32 bit overflow problem?

[Niaz]

I can't understand the overflow problem.
And can u plz tell me, is there any special method to solve this problem or just simply Adhok solution can do ?

[SilentStrike]

I wrote up my solution to the Pawn Chess problem on Algorithmist.

The 32 bit overflow problem is basically that you might overflow an int when doing bit arithmetic to pack a state into a 32 bit int.

[Christian Schuster]

I tried to solve this problem by using a minimax search. Each game state is assigned a value recursively:

Code: Select all

 0 <= N <= 19: BLACK wins after N moves
20 <= N <= 39: WHITE wins after (39-N) moves

Winning states get a 0 or 39, depending on the winner. For any other game state, BLACK uses the child state with the lowest score, while WHITE uses the highest.

This seems quite correct to me, and returns the correct output for any input in this thread. However, the judge disagrees (WA).

What's wrong? The "Algorithmist" solution seem quite similar, apart from using another encoding for the winner/moves value.

[Cho]

Here are some random input: 10838.zip
Please ignore those cases with "black (0)" as output, judge's input should not contain such cases.

[Christian Schuster]

Thank you. I had alpha-beta pruning enabled in my code, but this does not work if values are changed when passing them up the game tree. Something like this is necessary for the "fast victory/slow defeat" strategy to work.

Finally, I got AC in 2.38s using "normal" minimax.

[Krzysztof Duleba]

Actually, my number-one code (completely unoptimized, it could run at least two times faster) is using alpha-beta.