### nihal2001's blog

By nihal2001, history, 7 weeks ago,

So I am kind of stuck in a problem related to game theory!

Any help will be appreciated!

Problem:

Anjali and Vaibhavi are playing a game with a pile of N coins. In this game, Anjali and Vaibhavi make their respective moves

alternately, starting with Anjali.

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.

Given the initial number of coins in a pile, determine who would win the game.

Assume that both the players play optimally throughout the game.

Input Format:

First-line denotes t i.e. number of test cases

Next ‘t’ lines contain n where n is the number of coins in the pile as the game commences.

Output Format:

For each test case, print the winning player’s name (case sensitive).

Constraints:

1 <= t <= 10^5

1 <= n <= 10^18

Sample Input:

5

1

2

3

4

5

Sample Output:

Vaibhavi

Anjali

Vaibhavi

Anjali

Anjali

Explanation:

1st test case: Anjali can't make a move so Vaibhavi wins.

2nd test case: Anjali can remove 1 coin because 1&2=0 then 1 coin left so Vaibhavi can't make a move so Anjali wins.

3rd test case: Anjali can't make a move, so Vaibhavi wins.

And so on.

• +18

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by nihal2001 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by nihal2001 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by nihal2001 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Where did you get this problem?
•  » » 7 weeks ago, # ^ |   0 This problem was asked in a programming contest conducted on 1st march by coding ninjas!any help will be appreciated!
•  » » » 7 weeks ago, # ^ |   0 I think it's got something with the segments of 1s and 0s in the binary representation of n, but I can't really figure it out.Have you checked this thread though? https://discuss.codechef.com/t/coding-ninjas-problem-help-in-approach/86320/3
•  » » » 7 weeks ago, # ^ |   0 I think this approach kinda make sense.
 » 7 weeks ago, # | ← Rev. 6 →   0 Really Interesting problem for me!Note that this problem only relate to binary representation of n.If Anjali lose, we assign $f(n) = 0$, otherwise, $f(n - x) = 0$ for some $1 \leq x \leq n, x \And n = 0$. and we assign f(n) = $n - x$ for smallest such x.we can use following brute force code to compute small f(n). and see the case $f(n) = 0$ #include int main() { const int N = 10; int n = 1 << N; std::vector f(n); for (int i = 1; i < n; ++i) { for (int j = 1; j < i; ++j) if ((j & i) == 0) { if (f[i - j] == 0) f[i] = i - j; } } for (int i = 1; i < n; ++i) if (f[i] == 0) { std::cout << std::bitset(i) << "\n"; } return 0; }  F: if we delete all 11's and trailing 1's and end up with a value of 0（example: 0, 111, 11001, 1101101, 110000111100111) T: otherwise I claim that Anjali Win for T, and Vaibhavi win for FFirst it is easy to see that if n is odd, then $f(n) = f(n/2)$, so we may assume n is even. Secondly, if n belongs to case F, next step(if exist) $n - x$ must belongs to case T(easy to see) if n belongs to case T, if if the number of 1 in binary representation of n is even, we can move those 1 pair by pair(example: 101010010 -> 011000110), otherwise we can move the rightmost 1 to the end, and the rest pair by pair(example: 101010110 -> 011001101) Finally, Vaibhavi win for $n = 0$ which belongs to F, end the prove. #include #define watch(x) std::cout << (#x) << " is " << (x) << std::endl using LL = long long; bool solve(LL n) { while (n & 1) n >>= 1; while (n) { n >>= __builtin_ctzll(n); bool flag = false; while (n & 1) { n >>= 1; flag = !flag; } if (flag) return true; } return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int cas = 1; std::cin >> cas; while (cas--) { LL n; std::cin >> n; std::cout << (solve(n) ? "Anjali\n" : "Vaibhavi\n"); } return 0; } 
•  » » 7 weeks ago, # ^ |   0 Thanks for the reply, first of all! i was able to get your bruteforce solution , but your proof of the second part assuming cases F and t is not clear to me!it would be very helpful if you could explain it more clearly !
•  » » » 7 weeks ago, # ^ |   0 My comments document my entire thought process on this unfamiliar issue. No offense is meant in any way.If we are in the case of F, at which point 1's appear in pairs adjacent to each other, at which point no reasonable x will change the value of a 1 in an odd position, we observe that the leftmost changing bit necessarily happens to be a 1 in an even position that becomes a 0, which causes it to become TIf we are in the case of T, we can can make the original non-adjacent 1s next to each other, and if there is an extra 1 throw him to the far right.Translated with www.DeepL.com/Translator (free version)
 » 7 weeks ago, # |   +1 In this type of problems (Being Clueless) , I follow the below steps : 1. I generally do brute force for some small numbers. So,I have manually observed that,forN = 1,3,6,7,12,13,15,24 the answer is "Vaibhavi" for this problem. 2. I search that sequence in OEIS. For those who don't know aboot OEISSee this !3.Most of the times, I get a idea / formula about that pattern from OEIS. Like in this problem, the idea is Numbers in whose binary expansion there are no 1-runs of odd length followed by a 0 to their right. 4.I write code following that idea. For this problem, Here is my code. 5.I submit.P.S : This trick does not work always. Thank You ! SpoilerHope this helps.
•  » » 7 weeks ago, # ^ |   0 Hey, thanks for the reply! I didn't noticed that this can also be decoded using OEIS. but i was looking some more kind of proof of this.
•  » » » 7 weeks ago, # ^ |   0 You are welcome.