 SIMPLE

Game Theory

# PROBLEM:

Given integer N, Alice and Bob play the following game, with Alice moving first. The rules are as follows:

• Choose a positive integer y such that 2^y|N, and divide N by 2^y.
• If this is not possible, subtract 1 from N.

The player who can’t make a move loses. Determine the winner if both parties play optimally.

# EXPLANATION:

Let w(x) be the winner of the game with starting value x, if Alice plays first and both players play optimally. Consider w(x)=1 if Alice wins and 0 otherwise.

Let us find a suitable recurrence relation for function w.

Hint 1

A simple idea would be to try all moves and determine if Alice wins in at least one of those possibilities. Can you visualise the recurrence equations?

Pseudocode
int w(int N){
if(N == 0) return 0;
// We invert the result because Bob plays the next move.
if(N%2 == 1) return !w(N-1);

bool canWin = false;
for(int i = 2; N%i == 0; i *= 2)
if(!w(N/i)) canWin = true;
return canWin;
}


This naive solution can be sped up with memoization, which is sufficient to AC the first two test cases.

Hint 2

I claim that, if x is positive and divisible by 4, then w(x)=1.

Solution

Let y be the largest non-negative integer such that 2^y | x. Then, there are 3 cases for y:

• y=0 - The only move possible in this case is move two (subtracting 1 from x), so w(x)=1 only if w(x-1)=0 (we invert the answer since Bob plays the next move).

• y=1 - The only move possible in this case is dividing by 2, so w(x)=1 only if w(x/2)=0.

• y>1 - For this case, w(x) is always equal to 1, because

• if w(x/2^y)=0, Alice can divide x by 2^y and win, and
• if w(x/2^y)=1, Alice can divide x by 2^{y-1}, and Bob in the next move is forced to divide by 2 (see second point above), allowing Alice to play the next move on x/2^y and win.

The pseudocode is thus as follows:

int w(int N){
if(N == 0) return 0;
if(N%2 == 1) return !w(N-1); // case 1
if(N%4 != 0) return !w(N/2); // case 2

return 1; // case 3
}


It is easy to see that the algorithm iterates over each bit of N at most twice, which is efficient enough for the given constraints.

# TIME COMPLEXITY:

In the worst case (N=2^i-1), we process each bit in the binary representation of N twice, making the time complexity

O(2*d) \approx O(d)

per test case, where d is the number of bits of N.

# SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters

3 Likes

I have a bit different and possibly easier solution. The main idea is to transform the problem into a different one:

Alice and Bob have got a string S. Each letter in this string can be only
‘E’ or ‘O’. They decide to play a game. Alice and Bob make alternating
moves: Alice makes the first move, Bob makes the second move, Alice makes
the third one, and so on. The game continues until the string becomes
empty. The player who is unable to make a move loses. During each turn
a player can make one of the following moves:

• If the first letter in the string is ‘E’, then cut off any amount of
consecutive letters ‘E’ from the beginning of the string. The string
becomes shorter by at least one character or more.

• If the first letter in the string is ‘O’, then cut off just a single
letter ‘O’ from the beginning of the string. The string becomes
shorter by one character.

Predict the winner of the game if the game is played optimally by both
the players.

This way the number of DP states is very small and memoization-friendly. My practice C++ submission with cleaned up and fully commented code: Solution: 51620204 | CodeChef

3 Likes

Nice one easy to understand  I have solved it with different approach.
Solution: 51621529 | CodeChef
For that we need to observe the pattern in answer . If n is odd answer will be Bob and if n is even answer will be Alice , but the only case when it will not be the answer is when n+1 or n+2 is a power of 2 .

no need to travel further after searching 2 or more consecutive E since whichever player reached this state first will always win

Time Complexity of your solution is not O(1). It’s \Omega(\log{N}) and O(2\times \log{N}).

3 Likes

@suman_18733097
Thanks for pointing out the mistake i was not knowing that bitswise operation is of O(Total_bits).

1 Like

Time Complexity of your solution is not O(1). It’s Ω(log⁡N) and O(2×log⁡N).

Time complexity of @aadarshsinha’s solution is not O(1) only if we are moving into the bignum territory and allow insanely huge N. But with the specified N≤10^{18} constraint, it’s actually O(1). Basic arithmetic operations with 64-bit variables have O(1) time complexity on modern 64-bit processors, because each of them maps to a single processor instruction.

This is similar to how it’s possible to sort latin letters in a large string of length N with just O(N) time complexity by using counting sort. Outperforming the usual O(NlogN) general purpose sorting algorithms.

1 Like

hey, I tried solving using dp but I got only 10 points, can you please check if there is any problem with my approach
https://www.codechef.com/viewsolution/51609660

The problem statement is wrong. It says "a player can make one of the following moves” but a player is forced to make a type 1 move if he can. Disastrous problem. Don’t understand how the coordinators allowed such a wrong problem statement

In problem statement, its given that “a player can make one of the following moves”. So is it that the player can make 2nd move only if 1st is not possible or any move is allowed ?

hey, I tried solving using dp but I got only 10 points, can you please check if there is any problem with my approach
Solution: 51609660 | CodeChef

Your solution looks technically correct, but it’s just not optimal and performs a lot of unnecessary calculations. With the bottom-up approach, you are unnecessarily processing DP states, which are unreachable. For example, if N is 16, then the game can never reach states N=3, N=5 and so on, but you are still wasting processor time on them. A recursive top-down approach skips these DP states and this makes it faster.

Edit: Your solution is also missing the ios::sync_with_stdio(false); cin.tie(NULL); magic line for fast input/output and uses endl instead of a faster “\n”. This may be the biggest contributing factor for slow performance.

can someone tell me where am wrong ,I definitely know my approach is a lengthy one but its basic and still wrong, i am not getting why.
My solution: https://www.codechef.com/viewsolution/51698369
@ssvb

Can somebody plz tell where this solution goes wrong? Any test case? This solution is being partially accepted for the first two subtasks?

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod2 998244353
#define inf 100000000000000000
#define ll long long
#define ld long double
#define pb push_back
#define eps 1e-7
string alpha="abcdefghijklmnopqrstuvwxyz";

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1,tt=0;
cin>>t;
while(t--){
ll n,c;
cin>>n;
if(n==1){
cout<<"Alice\n";
continue;
}
c=n;
ll m=0;
vector<int> p;
while(n>0){
if(n%2){
n--;
}else{
ll cn=n,ct=0;
while(cn%2==0){
cn/=2;
ct++;
}
p.pb(ct);
n/=pow(2,ct);
}
}
//cout<<c<<" "<<p.back()<<endl;
int co=count(p.begin(),p.end(),1);
if(co==p.size()){
if(c%2==0) cout<<"Bob";
else cout<<"Alice";
}else{
if(c%2==0) cout<<"Alice";
else cout<<"Bob";
}
cout<<endl;
}
return 0;
}


The problematic part of your code is this line:

n/=pow(2,ct);


It breaks for some large N values, because “pow” function is doing floating point calculations and “double” data type can only store integer numbers up to 2^{53} without precision loss. I have replaced this line in your code with “n=cn;” and it got accepted: Solution: 51719339 | CodeChef

2 Likes

Thanks for telling the issue. I have learned a new thing regarding pow function and also the way you resolve the issue is nice.

second move can be made only if first move isnt possible.

N=10 {suppose}
X =2 , N/X =5 ; N=5 {is chosen by alice first time}
N -1 , N=4 { since X is not able to factor of N so Bob will substract one}
Now here is the problems comes in my mind
if Alice choses X= 2 i.e also a factor of N and pow(2) then
N=2
X=2 , N=1 {by Bob}
N-1 , N=0 { by Alice } so Bob loses here But if

When N = 4 and if Alice choses X=4 which is also factor of N and pow(2) then
N=1 ,
N-1, N=0 { by Bob} so Alice loses
and in question it is not mentioned that we have to choose X as greatest factor of N or anything else
so since both the solution is correct i think but answer of both contradict each other therefore i comment this please describe me why this happened.

The problem statement says:

Choose an integer X such that X can be expressed as 2^Y, Y≥1. The chosen X must also be a factor of N. After choosing an integer X which satisfies the mentioned criteria, the player will divide N by X.

A player can choose any X that satisfies the mentioned criteria. Alice has multiple options when N=4. Some of these options are optimal for Alice (she wins) and the others are not (she loses). The problem statement says:

Predict the winner of the game if the game is played optimally by both the players.

So Alice makes the best moves and Bob makes the best moves. But only one of them wins in the end. Your solution needs to figure out who is the winner.

2 Likes