CHCOINSG - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Vasya Antoniuk
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa

DIFFICULTY:

Simple

PREREQUISITES:

finding pattern, game theory, understanding of winning and losing positions

PROBLEM:

You have a pile containing n coins.
Two players play following game alternately. Each player in its turn can remove any prime power number of coins from the pile, i.e. p^x, s.t. p is a prime and x \geq 0. The player who can’t make his move loses the game. Find who wins the game.

QUICK EXPLANATION:

Second player will win iff N \, \% \, 6 = 0, otherwise first player will win.

EXPLANATION:

Solution based on finding pattern
We can find a pattern by writing a slow code to find the winner of the game for small numbers, say \leq 100. You can just implement the basic definition of winning/losing position in the game theory by writing a simple dp.

More formal solution
Let us try to see what happens for the game on some small examples.

For n = 1, first player will win.

For n = 2, 3, 5, first player will win as these numbers are prime.

For n = 4, the first player will also win as 4 = 2^2.

For n = 6, player can not remove 6 coins in his first turn, as 6 is not a prime power. Hence, whatever number of coins first player removes, he will end up with 1, 2, \dots, 5 coins, all of which are a wining positions for the other person. Hence, n = 6 is losing position for first player.

You can notice that numbers from n = 7 to 11, are also winning positions, as the first player can make a move such that remaining number of coins in the pile are equal to 6, which is a losing position.

For n = 12, the first player can win if he can move to some losing position, i.e. he could remove either 6 or 12 coins. He can’t remove any of these as they are not prime powers. So n = 12 is a losing position.

Similarly any multiple of 6 is a losing position, as you can’t make a move from n = 6 * k to any losing position, as you have to remove coins equal to some multiple of 6. A multiple of 6 can’t be a prime power, as 6 = 2 * 3.

Time Complexity:

\mathcal{O}(1) - Just check whether N \, \% 6 \, = 0 or not.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester
Editorialist

1 Like
2

I just used intuition to solve this one. Like the editorial says it, Chef would try to subtract a number x from N such that (N - x) would lead to a losing position. If he cannot find such x, then any value he subtracts from N will lead to a winning position for Misha.

My brute code force looks something like this

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 10001;

vector<ll> primes;
set<ll> prime_powers;
bool check[N+1];
bool dp[N+1];

int main()
{	
    memset(check,true,sizeof(check));
	for(ll p=2;p*p<=N;p++)
	{
		if(check[p])
		{
			for(ll i=p+p;i<=N;i+=p)
				check[i] = false;
		}
	}
	for(ll p=2;p<=N;p++)
		if(check[p])
			primes.push_back(p);
	
	prime_powers.insert(0);
	prime_powers.insert(1);
	for(ll i=0;i<primes.size();i++)
	{
		ll curr = primes[i];
		while(curr <= N*N)
		{
			prime_powers.insert(curr);
			curr *= primes[i];
		}
	}
	
	memset(dp,false,sizeof(dp));
	for(ll i=1;i<=N;i++)
	{
		if(prime_powers.find(i) != prime_powers.end())
			dp[i] = true;
		else
		{
			bool flag = true;
			for(ll p=primes.size()-1;p>=0&&flag;p--)
			{
				ll curr = primes[p];
				while(curr < i)
				{
					if(!dp[i-curr])
					{
						dp[i] = true;
						flag = false;
						break;
					}
					curr *= primes[p];
				}
			}
			if(flag)
			{
				if(!dp[i-1])
					dp[i] = true;
				else
					dp[i] = false;
			}
		}
	}

	for(ll i=1;i<=500;i++)
	{
		cout << i << " " << flush;
		if(dp[i])
			cout << "Chef" << endl;
		else
			cout << "Misha" << endl;
	}
	return 0;
}
3

For those finding it difficult to guess why ( N%6 ) was the losing condition, read Grundy numbers here. It will help you in solving this problem and other tougher problems of similar type. For example, if there had been more than 1 pile of coins.

4

You can think of it this way.

Trivially, 1, 2, 3, 4, 5 belong to the set of winning positions as they are all prime powers capable of reducing to 0 immediately.

6 on the other hand, can only reduce to winning positions and is therefore a losing position.

1: No multiple of 6 can reduce to any other multiple of 6 (including 0).
To reduce a number of the form 6m to 6n you need to remove 6 * (m - n) = 2 * 3 * (m - n) which is clearly not a prime power.

2: Any non multiple of 6 can be reduced to a multiple of 6.
For a number of the form 6 * k + l where l is either 1 2 3 4 or 5, we can subtract l (always a prime power) to reduce to a multiple of 6.

So, if you begin on a multiple of 6 your opponent can always put you back on a multiple of 6 no matter what you remove. Sooner or later you end up at 0.

If you begin on a non-multiple of 6, just reduce it to a multiple of 6 and now your opponent is on the losing position instead.

9 Likes
5

Formal proof using strong induction:
If 6|n then n is losing otherwise it is winning.

Let this statement be true for all numbers till 6k. We seek to prove for all the numbers till 6(k+1). This is induction on k.
Since 6k is losing, 6k+1,2,3,4,5 are all winning because they can be reduced to 6k (which is losing).
What remains to be proven is that 6k+6 can’t possibly be reduced to 6j for any j. For this, we must subtract a multiple of 6. But, no prime power can be a 0mod6, because it is always ±1 mod 6.
(6|6k,2|6k+2,3|6k+3,2|6k+4 so primes can only be 6k+1 or 6k-1.)

6

I used a different approach. First calculate the number of prime factors of N. If that is odd, first player wins. If even, second player wins. But I got a wrong answer. Isnt the logic right? Why? Where is the mistake. Please answer. Thank you.

7

for n=10,chef will remove 3 square coins i.e 9 coins,
remaining 1 coin will be removed by misha and he will win,as the problem clearly states that any 1 can remove 1 or prime power coins?
but in the editorial its given for n=10 also chef wins!!how come that’s possible?
please help

8

For n=10, Chef will remove 2^2 = 4 coins. So no of remaining coins will be 6(a losing position), and with Misha’s
turn to move next, she will lose.

9

both of the player play optimally(stated in question). That means chef can remove 2^2 = 4 coins. Misha will be left with 6 coins which means she will lose and chef wins.

10

I think editorial should contain your point. I too thought in this way