10536 - Game of Euler

All about problems in Volume 105. 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
windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

10536 - Game of Euler

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

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
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Location: Waterloo, Canada
Contact:

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

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
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

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

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

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. 8)

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

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

thank you John, I got ac now.

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

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.
Retired from SJTU Accelerator 2004

Folco
New poster
Posts: 3
Joined: Sun Apr 30, 2017 6:02 pm

Re: 10536 - Game of Euler

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?

Post Reply

Return to “Volume 105 (10500-10599)”