Recently I had participated in a contest on Hackerearth and came across this problem : Numbers Game

## Problem Statement Summary

This is a game between two persons : Robert and Ned .

There are two numbers N and K provided to us.

Robert Starts and picks a number , say x between 1 and K

Ned then picks a number (let’s call the number y) between x+1 and x+K

Now Robert’s turn again and he picks a number between y+1 and y+K and so on and so forth.

The first person to reach N wins. Both persons play *optimally*

We must determine who will WIN this game !!

## Sample Case Explanation

If N = 3 and K = 3 ,

Robert plays first and can choose a number between 1 and K , here he can choose 3 which is in fact N and ends up winning the game !

If N = 4 and K = 1 ,

Robert’s Turn : Has to pick between 1 and K , in this case , he can pick only 1 , Let us call this choice_1 = 1

Ned’s Turn : Has to pick between choice_1+1 and choice_1+K => In this case , 2 so

choice_2 = 2

Robert’s Turn : Has to pick between choice_2+1 and $choice_2+K =>$ 3 so choice_3 = 3

Ned’s Turn : By Similar Reasoning , choice_4 = 4 , which is actually N and game ends here making Ned the winner

Try to think a bit on how you would approach it before moving forward !

**My Approach , Thoughts and Observations**

Initially of course , my head was pretty muddled up because this was a short contest requiring you to find the solution really quick and I did not know how to simulate the players playing *optimally*

I was stuck.

Then I started thinking of *trivial cases* , if K >= N , obviously in the first turn itself when Robert plays and has to select a number between 1 and K , he can select N and conclusively win there and then

Then I was fumbling a bit with the idea of N-K as I thought if a player got to / chose N-K in any move , the player in the next move will win as he can select N in the next move .

The third thing that caught my attention was the low constraints on N and K , both were under 1001 indicating that an O(N^2) solution would pass.

Now a solution started forming in my mind :

Let’s look at the numbers from back to front i.e. from N to 1 , I took the example of N=10 and K=3 so we look at the sequence of numbers

Let’s begin :

If some player is at the number 10 , He is the WINNER so the

**same**person who obtains 10 is the winner . Next

If a player is at 9 or is forced to choose 9 , then the same player

**cannot**win because obviously in the next turn the other player will choose 10 which is N as the next player is allowed to choose from 9+1 to 9+K => 10 to 13 so

**different**or other player will win . Next

Say a player chooses 8 , then the

*next player*who plays after him can choose between 8+1 and 8+K which is 9 to 11 range , he chooses 10 obv so

*next*or

**different**player wins . Next

If a player is at 7 , the next player after him can choose from 8 to 10 , so he chooses 10 and

**different**or

**next**player wins . Then

Now the real fun begins , if a player is at 6 , the next player can choose from 7 to 9 (From 6+1 to 6+K )

Next player can choose b/w 7 to 9

But we already know that if a player arrives at 7 , the

**other**player will win

If a player arrives at 8 , the

**next**/

**other**/

**different**player will win

If a player arrives or chooses 9 ,

**other**or

**next**player will win

So if a player chooses 6 as we saw in the root node , no matter what the next player chooses , the **same** or **original** player , the one who chose *6* will WIN . Why ?

Let’s say Player A chooses 6

Player B chooses 7 then next turn Player A chooses 10

Player B chooses 8 then next turn Player A chooses 10

Player B chooses 9 then next turn Player A chooses 10

No matter what happens the original player who chose 6 (Be It Player A or B ) will WIN .

Next …

If some player chooses 5 will we lose/win ?

Let’s look at the choices the other player has

We know that if a player chooses 6 that player will win => same player

If a player chooses 7 , the other player will win

If a player chooses 8 , other player will win .

Now both of these players play optimally so if some player chooses 5 , the next player will look the options , 6 , 7 and 8 , he sees that if he chooses 6 , he wins so he takes that therefore the player who chooses 5 DOES NOT WIN i.e. the **different** player than the one who chose 5 wins .

Scenarios to prove

Player A chooses 5

Player B chooses 6

If Player A chooses 7 , 8 or 9 , in the next turn Player B can choose 10 and win .

Similar case when Player B chooses 5 , Player A chooses 6 , whatever Player B chooses , next turn Player A will win by choosing 10

The Player who chooses 5 DOES NOT WIN , the **different** or other player wins.

Similarly try by yourself to determine , if a player chooses 4 , does that **same** player win or **different** ?

and for 3 , 2 and 1

You will get this “result” array for indices 10 to 1 :

I denote 0 as **same** and 1 as **different** , as we’ve seen if a player gets to choose 10 , he wins so result[10] = 0

Similarly result[9] , result[8] , result[7] = 1 as the other player and not the player who chooses 7 , 8 , 9 wins and so on . Again the array is printed from index 10 to index 1

I just loop through this array from index 1 to K which is what Rob starts out with , if at least one SAME is present Rob wins else Ned wins i.e. if count of 0 in result array from indices 1 to K is greater than equal to 1 , then Rob WINS .

Why ? Because , if one of the value is same , then the guy who chooses that number , the same guy wins by our reasoning above !

**Code**

```
#include <bits/stdc++.h>
using namespace std ;
int main()
{
//0 denotes same and 1 denotes opposite
int t;
cin >> t ;
while(t--)
{
long long int n , k ;
int result[20000+1] ;
cin >> n >> k ;
//trivial case ?
if(k>=n)
cout << 0 << endl ;
else{
int same = 0 ;
for(int i=n ; i>=1 ; i--)
{
if(i==n)
result[i] = 0 ;
else if(i>=n-k && i<n)
result[i] = 1 ;
else
{
same = 0 ; //count of same
for(int sec = i+1 ; sec<=i+k ; sec++)
{
if(sec<=n && result[sec]==0)
same++ ;
}
if(same>=1)
result[i] = 1 ;
else
result[i] = 0;
}
}
same = 0 ;
for(int i=1 ; i<=k ; ++i)
{
if(i<=n && result[i]==0)
same++ ;
}
if(same>=1)
cout << 0 << endl;
else
cout << 1 << endl;
}
}
return 0 ;
}
```

And I got AC , I was so happy !!!

The question states to output 0 if Rob wins else 1 . The code above was the one I used in contest so it is not well documented and might be obfuscated . Let me know if I need to re-write a clean version will heavy comments if you don’t understand

**Doubts**

- Is my approach correct . I’ve read a lot of @tmwilliamlin’s comments about upsolving and trying questions that make you struggle and proving solutions and this question did make me struggle a bit and I was pretty happy instead of a pattern , I can justify why the solution worked
- Is there a faster way to solve this problem and how
- I know practise is the key to solving questions like these faster but what’s the most effective way to do guided practise on codechef

I’ve seen amazing coders like @ashishgup participate in this contest , it would be nice if they share their approaches

I’ve said it before that @viju123 and @ssjgz and now @tmwilliamlin are the best at this editorial business but I like to try my luck from time to time !

Let me know how it was .

- Enjoyed it ! Do more of these
- Hated It

0 voters

Cya Later!!