Game theory optimization

[N3wCDjzh]

I have been trying to understand game theory problems for a while and every time I try out a problem , I always end up using the brute force approach, can any one help me with this problem ??

Alice and Bob are playing a game of picking coins. They are given a large pile of N coins and an integer k. In the i^th move of any player,kⁱ coins are picked from the pile. A player who is not able to make the move during his turn loses. You are required to predict the winner of the game.

Note: In every turn, Alice plays first followed by Bob.

Constraints:
1<=T<=100
1<=N,k,<=10¹⁸

examples:
input:
4
10 3
14 2
18 10
37 5

output:
Bob
Bob
Alice
Alice

Explanation:
Test Case 1
In the first move: Alice first removes 3 coins, then Bob also removes 3 coins.
In the second move: Alice has to remove 9 coins but since only 4 are available, Alice loses and Bob wins.

Test Case 2
In the first move: Alice first removes 2 coins, then Bob also removes 2 coins
In the second move: Alice removes 4 coins, then Bob also removes 4 coins and only 2 coins remain.
In the third move: Alice has to remove 8 coins but it is not possible so Bob wins.

Similarly, the other two test cases can be followed.

My approach:

So, the first thing I did was to apply brute force and see when the value of N will become less than 0, and figure out which player wins, Time out as expected, then I thought of using GP and figuring out at which turn the value of N will become less than zero here's how I approached that:

We know that we need the ith turn where the value of N becomes less than 0, and we have k¹,k²,k³,k⁴... coins taken by each player, so we have:

N- (2*(k*(kⁱ-1))/(k-1)) <=0

which simplifies to:

i>= log(N(k-1)/(2k) +1 ) / log(k) // or take log base k ..

I used greatest Integer function for i and found the value of the i^th turn where we get winner...

Now to check our winner, we subtract GP of i-1^th turns from N, and the result we get, we will compare with kⁱ if less than this Bob wins else Alice wins.... Well, I got another time out :P.. I think its due to 10¹⁸ constraint on N and k, which is bad in log maybe... So..Any good approaches to tackle this? :)

[Grime]

I'm impressed you seem to be really very good in math! :O!!
I can't verify what you wrote because it seems like rocket science to me.

But here's the generic approach to solving such problems. Mostly I'm right on this one but keep in mind that I'm a noob.

So you have a pile of N coins. Alice and Bob take coins from the pile. When Alice and Bob take coins from the pile, we are basically subtracting from the pile.

Suppose Alice just finished taking 4 coins from the pile leaving 2 coins, and Bob needs to take 4 coins. 2-4 would give -2 which is not possible, which I think you understood as well.

Also keep in mind that how many coins is taken from the pile is dependent on this formula k^i, which again, you probably already know.

You could probably do this with math with little computation, but the general idea for solving such problems would be to use control statements (sometimes recursive functions also).

So how about something like this?

(pseudo code)

current turn = Alice's

for    (int i=0, Coins in Pile > 0, i++)

if (Alice's turn)
   winner = Bob
   current turn = Bob
else
  winner = Alice
  current turn = Alice

Coins in Pile = Coins in Pile - (k^i)

Hopefully if there are any improvements, somebody else can mention it.

I'm sure you will understand most of the code.
For k^i you can use pow() which is a function from cmath or, you could also write a for-loop (how would you do that??) but I'm not saying you should write a for-loop. Better rely on pow().

By the way we're using a for-loop over a while loop because we can use "i" the iterating variable, we could have also used a while loop it's the same thing.

Okay mostly you probably could understand everything but you might get confused in one detail - why we're assigning the winner to be the person who played last turn. If you do then I think you should think about it yourself ;^), that's how you learn and that's how you build your logic!

[Grime]

by the way timeout meaning?

[N3wCDjzh]

timeout, meaning it takes "forever" to compute the values...(Online ide's have a time restriction for output, if it takes greater than the allotted time, it shows timeout)

Okay, coming back to your idea. I think I got what you are trying to say, but what you're telling me to implement is a brute force approach which I already tried, but gives "timeout" or it takes very long time to compute large values... think of it yourself, in your pseudocode,

you take a for loop from coins till they become 0 and subtract coins in each turn, this surely take a while for computing values up to the order of 10¹⁸..??

[MikeyBoy]

timeout, meaning it takes "forever" to compute the values...(Online ide's have a time restriction for output, if it takes greater than the allotted time, it shows timeout)

You're talking about online coding competitions here, right?

[N3wCDjzh]

No, IDE's(NOT ALL IDEs), in general, have a time restrictions, like ideone.com, This code gives time out for certain inputs.. but yea in coding contests too. Basically my code is not efficient, need to optimise it..

[Grime]

I want to test your code. Where is 'c' defined? And what is test{} supposed to be (not what's inside but why you have written it there and like that)?

If you're actually expecting values of up to 10^18 for N and K then long long int is definitely not enough because you will have to store values like (10^8)^100 which is 10^800 (i.e k^i, if T in the constraint meant i).

long long int has an positive limit of 9,223,372,036,854,775,807 which is 10^9.

If you try storing values about that you will get integer overflow. So I wonder how you tested your program. Maybe that time out was because of integer overflow and not because of time constraints like you thought.

[ne555]

> I used greatest Integer function for i and found the value of the ith turn where we get winner...
¿how big do you expect `i' to be?
¿what parameters give you a bigger `i'?

> I think its due to 10^18 constraint on N and k, which is bad in log maybe
log increases quite slowly

[dutch]

Post the full code or a link to it.

[N3wCDjzh]

test{} is predefined code for taking test cases, sorry It wasn't clear in the code snippet that I provided...( simple int t;cin>>t; while(t--){//insert code here} )

No, T is not i, T is number of test cases..

i-> is the i^th turn that they will take on while taking the coins(i.e, it represent the turns)..defined by me , is the turn where we could potentially find the winner..

c-> THERE IS A TYPO IN MY CODE, I FORGOT I CHANGED c to i(but forgot to change in one place)...

i-> could be as large as c, according to my code.. where I defined the formula for c..
bigger k might give me bigger i..

NOTE: In my code i is simply the turn where we could find the potential winner(or i in my code= c, Soryy for confusing you guys)

So, There is no 'c' in my code... I used it just to explain that there is an i where we could find the potential winner...

It might be that I am running into an overflow error, then the solution will not be achieved from my approach I think ?? any suggestions ???

[dutch]

18 digits of precision are not guaranteed for a double. Try long double (Intel long double guarantees 18 digits). And make n and k long double, too. Although if they are both huge then n * (k-1) may overflow; well, not "overflow" exactly (as a floating point), but lose precision. I don't know if that matters.

It must be your ipow function that's causing TLE. If you're going for efficiency, the last thing you want is a non-tail-recursive function when a simple loop would do! But an even more efficient ipow is something like this:

LL ipow(LL base, LL exp) {
    LL result = 1;
    while (true) {
        if (exp & 1) result *= base;
        exp >>= 1;
        if (!exp) break;
        base *= base;
    }
    return result;
}

But those incredibly high constraints could obviously be a problem.
Do you have a link to this problem online?

BTW, your "test" thingy is kind of silly! ;)
And the usual way to "include everything" in competitive programming is

#include <bits/stdc++.h> 

EDIT: As far as the math goes I think it should be more like this:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        long double n, k;
        cin >> n >> k;
        
        long double x = ((k - 1) * n + k) / 2;
        x = floor(log(x) / log(k));
        n -= 2 * (pow(k, x) - k) / (k - 1);

        if (n >= pow(k, x))
            cout << "Alice\n";
        else
            cout << "Bob\n";
    }
}

[N3wCDjzh]

long double did the trick for most of the part. wow.. thanks for helping in that regard.. Yet some test cases are not passing :/ maybe some boundary cases ??

[N3wCDjzh]

ok, cool, got it k=1 was boundary case to be taken care of. Thank you everyone for helping me understand this problem and dealing with large inputs :)

[Browni3141]

These inputs are actually really small for any k >= 2 due to exponential growth. The naïve approach of playing out the game and determining the winner is easily fast enough for any 2 <= k <= 10^18. Only k == 1 is slow because the number of stones removed grows linearly but that's easy to calculate. This problem would be more interesting with larger constraints.