# K_POWGAME - Editorial

Author: shivanshj
Tester & Editorialist: iceknight1093

2628

Observation

# PROBLEM:

Shivansh and Tina play a game; Shivansh goes first.
They have a number with them, initially N. On their turn, a player should pick a non-negative integer power of K that doesn’t exceed N, and subtract it from N.

Under optimal play, who wins?

# EXPLANATION:

With two-player games like this, It often helps to analyze some small cases first, for example with K = 2, 3, 4, \text{ or } 5.

Some simple analysis reveals that when K = 3, Shivansh can always win if N is odd, and loses otherwise.
This is because 3^x is odd no matter what the value of x is. So:

• If N is odd, an odd number of turns will have passed when N reaches zero.
This means Shivansh made the last move.
• If N is even, an even number of turns will have passed when N reaches zero.
This means Tina made the last move.

In fact, the above analysis holds true for all odd K: Shivansh wins if N is odd, and loses otherwise.

For even K, let’s look at what happens for small N.
Clearly, Shivansh can win if N = 1, 3, 5, 7, \ldots, K-1 and Tina can win N = 0, 2, 4, 6, 8, \ldots, K-2.
That’s because for these values of N, the only possible move is to subtract 1; so the winner is decided by parity.
However, Shivansh can win N = K by just subtracting K.

After this,

• Tina wins N = K+1, since Shivansh must subtract either 1 or K and Tina subtracts the other one.
• Shivansh wins N = K+2, by subtracting 1 and giving N = K+1 (a losing state) to Tina.
• Tina wins N = K+3: whether he subtracts K or 1, 3 and K+2 are both winning states for Tina.
• Generally, Tina wins K+1, K+3, K+5, \ldots, 2K-1; and Shivansh wins K+2, K+4, \ldots, 2K
• However, Shivansh wins 2K+1; since he can subtract K on his turn and give K+1 to Tina (which is losing, as noted above)

You might notice that this process is consistent in ‘blocks’ of length K+1 starting from 0.
That is, in each such block, Tina wins the even positions and Shivansh wins the odd ones; except Shivansh wins the last position despite it being even.

This is indeed the pattern for Shivansh’s win condition.
That is, let r = N \pmod {K+1}, i.e, r is the remainder when N is divided by K+1.
Then, Shivansh wins if r is odd or r = K, and loses otherwise.

Proof

We’ll prove this by induction, though the basic idea was outlined above.

For the base case, we already know it’s true for the segment [0, K+1), as noted above.
Now, assume it’s true for [0, x\cdot(K+1) ), and we’ll prove it’s true for [0, (x+1)\cdot(K+1)).

The main observation required here is the fact that K^x is always either 1 or -1 modulo (K+1), which is easy to see (in fact, since K \equiv -1 \pmod {K+1}, the powers of K alternate between 1 and -1).
So,

• x\cdot (K+1) is a losing state: no matter what move is made, we move to either 1 \pmod{K+1} or K \pmod {K+1}, and in the range \left[0, x\cdot (K+1)\right); by the inductive hypothesis these are winning states for the opponent.
• x\cdot (K+1) + 1 is a winning state: subtract 1 to put the opponent in a losing state.
• x\cdot (K+1) + 2 is a losing state: either we subtract 1 and move to (x\cdot (K+1)+1), which is winning for the opponent; or we subtract move to an odd value modulo K+1 in the range [0, x\cdot (K+1)) which is still winning for the opponent.
• Extrapolating this, all odd numbers are winning and even numbers are losing.
• However, x\cdot (K+1) + K is winning, since we can subtract K.

This takes care of all integers in the range [x\cdot (K+1), (x+1)\cdot (K+1)); and so we’re done.

In fact, this pattern holds true for odd K as well, since we didn’t really use the parity of K anywhere.

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

Author's code (C++)
                    //Enjoying CP as always!
// NO FAREWELL: KEEP GOOGLE COMPETITIONS ALIVE
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
//freopen("small_tests_input.txt", "r", stdin);
//freopen("small_tests_output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--) {
int n,k;
cin>>n>>k;
int z = n%(k+1);
if((z&1LL)  || z==k) {
cout<<"Shivansh\n";
} else {
cout<<"Tina\n";
}
}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
print('Shivansh' if n%(k+1) == k or (n%(k+1))%2 == 1 else 'Tina')

2 Likes

#include
#include <string.h>
using namespace std;

//converting to equivalent number with base ‘b’
long long int convert_base(long long int base,long long int inputNum) {

long long int count=0;
while (inputNum > 0) {
count += (inputNum % base);
inputNum /= base;
count=count%2;
}
count=count%2;
return count;
}

int main() {
int t;
cin>>t;
while(t–)
{
long long int n,k;
cin>>n>>k;
if(k>n)
{
if(n%2==0)
{
// cout<<n<<endl;
cout<<“tina”<<endl;
}
else
{
// cout<<n<<endl;
cout<<“shivansh”<<endl;
}
}
else if(n==k)
{
cout<<“shivansh”<<endl;
}
else
{
long long int count=convert_base(k, n);

        if(count%2==0)
{
cout<<"tina"<<endl;
}
else
{
cout<<"shivansh"<<endl;
}
}
}
return 0;


}

My code is passing 3 testcases and failing in two test cases.
Can someone tell which edge cases I am missing

That’s because N\mod (K+1) equals K. That’s why I’m the winner ( ). Have you read the editorial and proof?

@shivanshj but according to the question when we solve the test case the right answer would be (tina) not (shivansh)

Why do you think “Tina” is right answer? The logic of editorial clearly states that “Shivansh” should be the right answer.

@shivanshj i’m not talking about editorial, according to the question when we solve the question the right answer would be (tina) as shown in the below image. (shivansh) cannot play game as (N) become 0 so (tina) would be the winner.

You seem to be thinking that the highest power of 4 should be subtracted each time. But any power of 4 can be subtracted. So that leads to multiple possibilities, all of which you have to figure out. I’d suggest that you try out easier problems on game theory before trying this problem