## 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

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??

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
i see, thanks for you hint

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm
but still get wrong answer...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
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

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

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:
is there any closed form solutions that requires O(1) time and memory?

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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:
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
I misunderstand the problem
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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
s1363 wrote:I misunderstand the problem
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
Thanks emotional blind. I have a silly mistake