nihal2001's blog

Need Help In Game Theory Problem??
By nihal2001, history, 4 years ago, In English

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.

  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where did you get this problem?

→ Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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 <bits/stdc++.h>
int main() {
	const int N = 10;
	int n = 1 << N;
	std::vector<int> 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<N>(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 F

First 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 <bits/stdc++.h>
#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;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 !

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 T

      If 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)

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 OEIS

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 !

Spoiler
→ Reply