11249 - Game

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

Moderator: Board moderators

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

11249 - Game

Post by ziliang » Sun Jul 29, 2007 12:55 pm

I solve it like this:
if(a>b)swap(a,b);
if(a*(k+2)==b) it_is_losing
else it_is_winning



Am I missing something?? or I used a wrong algorithm??

please help me.
不鸣则已,一鸣惊人.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 29, 2007 1:05 pm

You missed something. Some part of your idea is right though.
But think why for a = k+2 and b = (k+2)*(k+2) it is a winning position (you would print it is a losing position).

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

Post by ziliang » Sun Jul 29, 2007 1:33 pm

i see, thanks for you hint :P
不鸣则已,一鸣惊人.

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

Post by ziliang » Sun Jul 29, 2007 1:56 pm

but still get wrong answer...
不鸣则已,一鸣惊人.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 29, 2007 2:51 pm

Try to check against a brute force program with small values (for example a, b <= 1000), that should be sufficient to find the mistake(s).

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun Jul 29, 2007 5:49 pm

I started reading this article very recently (and then stopped for some reason, go me):
http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm

Wythoff's game is this problem with k=0.

I solved it but it didn't "feel right". I generated first 20 winning pairs for k<=4, found pattern and just generated them all.

I, too, started with (1,k+2) pair and then tried to figure out something out of it, but then gave up. Is there a way of telling who wins for any given k,a,b? Or that limit was there just so there could be alternate solutions?

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

WA

Post by baodog » Mon Jul 30, 2007 12:53 am

I found the way to generate the piles is (n, (k+2)*n) where n is the least unused number (see code), but I'm getting WA.... maybe I'm missing something obvious.

Code: Select all

Wrong Code
Last edited by baodog on Mon Jul 30, 2007 2:19 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 30, 2007 1:30 am

I found the way to generate the piles is (n, (k+2)*n) where n is the least unused number
No, that's not it.

Just for reference, here are the first few losing positions for k=1:
0 0, 1 3, 2 6, 3 1, 4 10, 5 13, 6 2, 7 17, 8 20, 9 23, ...

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Limit of b/a

Post by baodog » Mon Jul 30, 2007 2:18 am

Given two piles (a,b) with b>a, that is LOSING for k=1,
The limit of b/a as a->+infinity,
appears to go to 1+sqrt(2).

So for k=1, there is O(1) solution.

a -> floor(sqrt(2)*m)
b -> floor( (2+sqrt(2))*m)

for some integer m.

Not sure about higher k !!!
Last edited by baodog on Mon Jul 30, 2007 3:24 am, edited 2 times in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Jul 30, 2007 3:07 am

is there any closed form solutions that requires O(1) time and memory?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Jul 30, 2007 3:56 am

Time Complexity: O( min(a,b) )
Space Complexity: O(1)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 30, 2007 4:03 am

I've found this paper - http://www.wisdom.weizmann.ac.il/~fraen ... mhoff5.pdf

Essentially it says the following about our problem:
Let n=k+1, phi=(n+sqrt(n^2+4))/2, alpha=1+1/phi, beta=1+phi.
Then the losing positions are (floor(alpha*x), floor(beta*x)), for x=0,1,2,...

So, this is the O(1) solution :)

s1363
New poster
Posts: 2
Joined: Mon Jul 30, 2007 3:02 pm

Post by s1363 » Mon Jul 30, 2007 3:14 pm

I misunderstand the problem :oops:
when a = 2 and b = 5 and k = 1 I consider below scenario:
first we have (2, 5) and Alic take 2 stones from b and one stone from a so we have (1, 3) then Bob knows he cannot win but He has no choice for winning (if he remove one stone from a, Alic win. If he removes at least on stone from b Alice win) So Alice is the winner but sample output differ :-?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Jul 30, 2007 3:25 pm

s1363 wrote:I misunderstand the problem :oops:
when a = 2 and b = 5 and k = 1 I consider below scenario:
first we have (2, 5) and Alic take 2 stones from b and one stone from a so we have (1, 3) then Bob knows he cannot win but He has no choice for winning (if he remove one stone from a, Alic win. If he removes at least on stone from b Alice win) So Alice is the winner but sample output differ :-?
But you are right..
2 5 is winning position
sample input also says so..

1
1 4
2 5 - WINNING
2 6 - LOSING
1 3 - LOSING
1 4 - WINNING

s1363
New poster
Posts: 2
Joined: Mon Jul 30, 2007 3:02 pm

Post by s1363 » Mon Jul 30, 2007 3:50 pm

Thanks emotional blind. I have a silly mistake :oops:

Post Reply

Return to “Volume 112 (11200-11299)”