10536 - Game of Euler

windows2k · Post by **windows2k** » Tue Jul 29, 2003 6:21 am

My thought is backtracking. But it's too inefficent.
Try to find all possible solutions.
But it looks like a nim game, should have a faster method
Could someone give me some hints,thx:)

LittleJohn · Post by **LittleJohn** » Tue Jul 29, 2003 6:29 am

Memorization. Don't call dfs again if the current state is known because one state will always have only one possible answer.

konsept · Post by **konsept** » Tue Jul 29, 2003 8:49 am

the correct term is MEMOIZATION, not memorization.
it's a form of Dynamic Programming (top-down instead of bottom-up).

LittleJohn · Post by **LittleJohn** » Tue Jul 29, 2003 10:36 am

Sorry, I used memoization at first (p10157 related post). But I saw somebody use the word "memorization". It indeed confused me.

windows2k · Post by **windows2k** » Tue Jul 29, 2003 11:51 am

LittleJohn wrote:Sorry, I used memoization at first (p10157 related post). But I saw somebody use the word "memorization". It indeed confused me.

Sorry, What's the output for the input
10

....
....
....
....

.X..
..X.
XX..
...X

...X
.X..
X..X
..XX

X..X
....
....
X..X

....
.XX.
.XX.
....

XXXX
X..X
X..X
X...

.XX.
X..X
X..X
.XX.

..XX
XX..
...X
X...

....
X..X
.X..
...X

XXXX
....
..X.
XXX.

Thx in advance

LittleJohn · Post by **LittleJohn** » Tue Jul 29, 2003 12:15 pm

my AC program gives

Code: Select all

LOSING
WINNING
WINNING
WINNING
LOSING
WINNING
WINNING
LOSING
LOSING
LOSING

Good Luck

sharklu2000 · Post by **sharklu2000** » Fri Aug 01, 2003 5:10 pm

LittleJohn wrote:my AC program gives
Code: Select all
LOSING
WINNING
WINNING
WINNING
LOSING
WINNING
WINNING
LOSING
LOSING
LOSING
Good Luck

Hi LittleJohn, could you tell me how your program took the first step in
the last test case? My program took the first step as follows
XXXX
. XX .
. . X .
XXX .
I really don't know why it will lose.

LittleJohn · Post by **LittleJohn** » Sat Aug 02, 2003 5:23 am

Hi sharklu,
It's the only trick in this problem.
Something wrong(illegal) with your first step,
just read the problem description and take a look at the picture again.
think about it.

sharklu2000 · Post by **sharklu2000** » Sun Aug 03, 2003 4:45 pm

thank you John, I got ac now.

hujialie · Post by **hujialie** » Tue Oct 07, 2003 11:21 am

Hello,I have just passed this problem with a very
long(>140 lines) and slow (>0.8sec) program.
Would anyone with a faster solution like to exchange
codes with me?I'd like to make an improvement.
Mail me.Thanks in advance.

Folco · Post by **Folco** » Mon May 01, 2017 3:38 am

I use 2^16 to model the board and using minimax algorithm to solve it.. but i got WA...
Did it has special case?

OJ Board

10536 - Game of Euler

10536 - Game of Euler

Re: 10536 - Game of Euler