Coding Ninjas problem help in approach

The problem can be accessed here [Contest has ended at 9 pm]
Problem-
A nd B are playing a game with a pile of N coins. A starts the game and each player plays alternatively.
In a turn, a player can remove x coins from the pile if x satisfies :
1<= x <= n
x & n == 0 (bitwise and of x and n is 0)
where 'n' is the size of the pile in the current turn.
The player who is unable to make a move loses the game.
Determine winner of game if both the players play optimally.Initially N coins are given.
Constraints:
1 <= t <= 10^5
1 <= n <= 10^{18}

Sample Input:
3
3
4
5
Sample Output:
B
A
A

Can someone help me with the approach

Can someone help? @ssjgz @ssrivastava990 @akshitm16 please help me with the approach.

Hey I was doing the same problem for code ninjas. I didn’t get the answer for this and wasn’t able to do it. Kind of a hint I could give but that is all I have.

You see in game theory we have two states for game. Winning State and Non-Winning state. You can find that all Non-Winning states are 1,3,7,15 and so forth, which follows the patter of 2^n-1. where 1<=n<=64. That are all the non-winning states. So if A comes on a Non-Winning state. There exists no number with which n&x==0.

if for any unset bit in n there are odd set bits before it than A wins otherwise B wins.

Can you help me with the proof of this

My idea was that for any arbitrary number N(eg. 18), if you take the next highest power of 2-1(31 for this example), and XOR it with N(13), you get the number which if you & with N you get 0(18 & 13 == 0).
or N&(N^(pow(2, log2(N)+1)-1)) == 0;
now you use this (N^(pow(2, log2(N)+1)-1), lets call it X, and subtract it from N untill you come to a non-winning state as mentioned above.
But this code was marked incorrect when i wrote it, and i dont understand why.

That’s giving WA . I submitted that exactly same solution.

I didn’t think much. Just wrote a stupid brute force which works fast only till N=10^4.

See if you can decode some pattern out of it and later prove it-

Code
def calc(i,start):
    global dp
    if i and not (i+1)&i:
        #B wins
        dp[i]=1
        return start^1
    if dp[i]!=-1:
        return start^dp[i]
    for j in range(1,i):
        if not j&i:
            val=calc(i-j,start^1)
            if val==start:
                dp[i]=0
                return start
    dp[i]=1
    return start^1

N=10**4
dp=[-1 for i in range(N+1)]
# 0 means A wins
# 1 means B wins

for i in range(1,N+1):
    # A starts the game
    calc(i,0)

# uncomment to see dp values
# print(dp)
# for i in range(1,N+1):
#     print(i,dp[i])


t=int(input())
for _ in range(t):
    n=int(input())
    if dp[n]:
        print("B")
    else:
        print("A")

Btw, where to submit code? The link is not accessible for me.

Edit-

Values where B wins-

“Numbers in whose binary expansion there are no 1-runs of odd length followed by a 0 to their right.”

B wins

I found the pattern as set bits occurs as consecutive pair. And least significant pair may be unpaired.
I don’t to prove this, it was just an observation.

Ex: 11001101 , 1111011, 1100011 are valid
1011, 110100, 100001, 111000 are invalid

Final code

def calc(i,start):
    global dp
    if i and not (i+1)&i:
        #B wins
        dp[i]=1
        return start^1
    if dp[i]!=-1:
        return start^dp[i]
    for j in range(1,i):
        if not j&i:
            val=calc(i-j,start^1)
            if val==start:
                dp[i]=0
                return start
    dp[i]=1
    return start^1

# N=10**4
# dp=[-1 for i in range(N+1)]
# 0 means A wins
# 1 means B wins

# for i in range(1,N+1):
#     # A starts the game
#     calc(i,0)

# uncomment to see dp values
# print(dp)
# for i in range(1,N+1):
#     if not dp[i]:
#         print(i)


def check(n):
    if not (n+1)&n:
        # B wins
        return 1
    count=0
    zeropassed=0
    for i in range(65):
        if not n&(1<<i):
            if count%2 and zeropassed:
                return 0
            count=0
            zeropassed=1
        else:
            count+=1
    return 1

# for i in range(1,N+1):
#     assert dp[i]==check(i)

t=int(input())
for _ in range(t):
    n=int(input())
    if check(n):
        print("B")
    else:
        print("A")
    # if dp[n]:
    #     print("B")
    # else:
    #     print("A")

Can you submit to see if that’s correct? I didn’t think of the proof but this should work.

And i got full score using this approach so there is definitely some mistake in your implementation.

For a particular n you will subtract x that have set bits where n have unset bits.So first thing to observe is that if at some point n has only consecutive set bits starting from lsb than we can’t subtract anything and that player loses.Now suppose n is like 1110011 so you can subtract 0001000 ,0001100 or 0000100.Upon subtracting the given values we can get 1101011, 1100111 or 1101111. So three is the minimum number of subtractions we need to get all the consecutive set bits.

Now consider n as part of continuous 1’s than 0’s than 1’s and so on.And we have to gather all the set bits together.As we have seen the number of subtraction ie the number of moves depends on the set bits before the unset bits and for A to win he needs odd moves so the optimal move for him would be to subtract 1 from all the unset bits that have odd set bits before them and by doing so upon player B turn there will be no unset bits with odd set bits and hence he doesn’t have any winning move.

1 Like

Yes, its AC. I just submitted your code.

Got it. Thank you so much

can someone tell me what im doing wrong in my approach that i mentioned above?