896 - Board Game

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

896 - Board Game

Post by .. »

The problem says that the following is draw:

Code: Select all

But if W moves first, I think that W can win....
What's wrong??

Code: Select all

round 1 .W.W..R..WRR
round 2 .W...WR..WRR

round 3 .W...W.R.WRR  (R move 1 right)
round 4 .W....WR.WRR
round 5 .W....W.RWRR
round 6 .W.....WRWRR  (W win)

round 3 .W...W..RWRR  (R move 2 right)
round 4 .W.....WRWRR  (W win)

09/09/04 This bug in description has been fixed
Last edited by .. on Thu Sep 09, 2004 1:01 pm, edited 1 time in total.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

New poster
Posts: 2
Joined: Fri Oct 11, 2002 9:11 pm

Post by Alvaro »

I agree. It would be a draw if you add an extra empty square at the end of the row, though.

New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

896 Board Game

Post by krijger »

After working on it for quite a long time, I still get WA on this problem. I've written a brute-force solver and for lengths up to 15, the answers match.

I seriously suspect a bug in the input format / testdata, or there must be very tricky cases, which only show at lengths > 15. Could someone check the I/O, or give me a tricky case?

little joey
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I don't think Per reads these forums anymore, but you could try to send him a PM or email. Or else, mail Carlos (via problemset@uva.es).

I haven't realy tried this one, although I have been given it much thought. My guess is that there has to be something heuristic involved (it's a zugzwang problem, like 4-in-a-row) but never could find anything useful.

New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

Ok. I will do that.

I figured out it is a sort of nim game, but with lots of special cases.

Post Reply

Return to “Volume 8 (800-899)”