11249 - Game

[ziliang]

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]

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]

i see, thanks for you hint

[ziliang]

but still get wrong answer...

[Adrian Kuegel]

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]

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]

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

[mf]

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]

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

[sclo]

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

[emotional blind]

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

[mf]

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]

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]

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]

Thanks emotional blind. I have a silly mistake