PRIGAME - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Divyam Singal
Testers: Felipe Mota and Radoslav Dimitrov
Editorialist: Divyam Singal

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Game Theory, Number Theory

PROBLEM:

Chef and Divyam are playing a game with the following rules:

  • First, an integer X! is written on a board.
  • Chef and Divyam alternate turns; Chef plays first.
  • In each move, the current player should choose a positive integer D which is divisible by up to Y distinct primes and does not exceed the integer currently written on the board. Note that 1 is not a prime.
  • D is then subtracted from the integer on the board, i.e. if the integer written on the board before this move was A, it is erased and replaced by A−D.
  • When one player writes 0 on the board, the game ends and this player wins.

Given X and Y, determine the winner of the game.

QUICK EXPLANATION:

Let A denote the product of first (Y+1) primes. Then the first player wins if X! is not divisible by A, else second player wins.
Let the number on the board currently be N. This game can be considered as having two states, one in which N is divisible by A, call it the divisible state and other where N is not divisible by A, call it the not divisible state.
We can’t go from a divisible state to a divisible state after a move as it would mean the number which has been subtracted should also be a multiple of A which is not possible.
And we can go from a non divisible state to a divisible state, by removing the remainder of dividing N by A.
So if X! is not divisible by A, the first player can always play to ensure he gets a non divisible number each time, to which he converts it into a divisible number for the second player. As 0 is a divisible state, the first player would win. Similar strategy works for second player in the case X! is divisible by A.

EXPLANATION:

We introduce a variable A, which is the product of the first (Y+1) primes.
Let us get some intuition as to why we have chosen such a number A.

Lemma 1: The difference between two multiples of A will have at least Y+1 distinct prime factors.

Proof of Lemma 1

Let the first Y+1 prime factors be P_1,P_2, \dots ,P_{Y+1} and let the two multiples of A be a_1 and a_2
We can write a_1 and a_2 as-
a_1=K_1P_1P_2\dots P_{Y+1}
a_2=K_2P_1P_2\dots P_{Y+1}
where k_1 and k_2 are some positive integers.

Then a_1-a_2=(K_1-K_2)P_1P_2\dots P_{Y+1}, and hence it has at least Y+1 distinct prime factors P_1,P_2, \dots ,P_{Y+1}.

Lemma 2: The remainder after dividing a non-multiple of A by A will have at most Y distinct prime factors.

Proof of Lemma 2

Let a non-multiple of A be a.
By the Euclid’s Division lemma, we can write a=bA+r, where 0 \le r < A.
For the sake of contradiction, let us assume that the remainder r is divisible by at least Y+1 primes.
The product of at least Y+1 distinct primes will be more than A, as A is the product of the first Y+1 primes. This will lead to contradiction due to the fact that r<A.

We now define the two states of the game. Let the number on the board currently be N.
The state is called divisible if N is divisible by A and the state is called non-divisible if N is not divisible by A.

Let us think about the transitions in these two states. Here transition means a change in state after a player’s move.

Lemma 3: From a divisible state, we are forced to go to a non-divisible state.

Proof of Lemma 3

For the sake of contradiction, let us assume that we can go from a divisible to a divisible state. Using Lemma 1, we know that the difference between them have at least Y+1 prime factors, which is not possible as a move consists of subtracting a number having at most Y prime factors.
So from a divisible state, we can only (forcefully) go to a non-divisible state.

Lemma 4: From a non-divisible state, we can go to a divisible state.

Proof of Lemma 4

From Lemma 2, we know that the remainder after dividing a non-multiple by A will have at most Y distinct prime factors. Subtracting the remainder of dividing N by A will be a valid move as it will have at most Y distinct prime factors. The number after subtracting the remainder will be a multiple of A.

Now in our game, having a non-divisible state is a winning state. This is because 0 is a divisible state, so the player having a non-divisible state can only arrive to 0.

Using Lemmas 3 and 4, we observe that a player can maintain the non-divisible state. This is because from a non-divisible state, the other player will get a divisible state. And from the divisible state, the player is helpless, leaving a non-divisible state for this initial player.

So Chef i.e. the first player will win the game if he starts with the non-divisible state, otherwise Divyam i.e. the second player will win the game.

Our problem reduces to just checking whether X! is divisible by the product of first Y+1 primes or not.
To check this, we will first find all the prime numbers from 1 to 10^6. This can be done by using the Sieve approach.

Sieve method
for(int i=0;i<1000001;i++)
{
    prime[i]=1;    //initially every number is marked as prime
}
for(int i=2;i*i<=1000000;i++)
{
    if(prime[i]==1)
    {
        //marking multiples of i as non-prime
        for(int j=2*i;j<=1000000;j+=i)
        {
            prime[j]=0;
        }
    }
}
//Time complexity is O(nlogn)

Next we will find the prefix sum of the primes, which stores the count of primes not greater than it.
This is the pre-build work, which can be done in O(XlogX).

Then for each test case, all we do is compare the pref\_sum[X], which we calculated above with Y+1. If it is smaller, Chef (first player) wins and otherwise Divyam (second player) wins.
So each test case takes O(1) time.

The total time complexity is O(XlogX+T).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define vll vector<ll>
#define ld long double
#define pll pair<ll,ll>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
const int MOD=1000000007; //998244353
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll prime[1000001],pre[1000001];
    for(int i=0;i<1000001;i++)
    {
        prime[i]=1;
    }
    for(int i=2;i*i<=1000000;i++)
    {
        if(prime[i]==1)
        {
            for(int j=2*i;j<=1000000;j+=i)
            {
                prime[j]=0;
            }
        }
    }
    pre[0]=0;
    pre[1]=0;
    for(int i=2;i<=1000000;i++)
    {
        pre[i]=pre[i-1]+prime[i];
    }
    ll t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        ll x,y;
        cin>>x>>y;
        if(pre[x]<y+1) cout<<"Chef";
        else cout<<"Divyam";
        cout<<"\n";
    }
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long a;
	cin >> a;
	return a;
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	const int maxy = 20000000;
	vector<int> factor(maxy + 1, -1), primes;
	for(int i = 2; i <= maxy; i++){
		if(factor[i] == -1){
			primes.push_back(i);
			for(int j = i; j <= maxy; j += i){
				if(factor[j] == -1)
					factor[j] = i;
			}
		}
	}
	int t = readIntLn(1, 1000000);
	while(t--){
		int x, y;
		x = readIntSp(1, 1000000);
		y = readIntLn(1, 1000000);
		if(x >= primes[y]) cout << "Divyam\n";
		else cout << "Chef\n";
	}
	return 0;
}
5 Likes

@div5252 :+1: , Nice editorial.

3 Likes

Can anyone help me locate the mistake in my solution 42627229
I used sieve to compute all primes below max X and then count primes

2 Likes

same problem . some one plz expalin why is it giving TLE.
https://www.codechef.com/viewsolution/42838020

1 Like

The last part is unnecessarily rushed.

Our problem reduces to just checking whether X! is divisible by the product of first (Y + 1) primes or not.

So far, so good. But then, how does jump between “checking for divisibility” to “computing prefix sum and checking for smaller or larger happen”? Moreover, why are we only computing primes till X when we were talking about divisibility of X!. It might seem obvious to some, but is really not for most people reading the editorial.

Some explanation : First, observe that every prime factor of X! is also a prime factor of some number <= X. Next, every prime factor of a number k <= X is also a prime factor of X!. In other words, X! contains only (and all) the prime numbers less than or equal to X as its prime factors.

For the second part, for primes p_i, notice that a number of the form p_1 \cdot p_2 \cdots \cdot p_k would divide a number n, IFF each and every p_i is a prime factor of n. Consequentially, if the largest prime factor of n is less than the largest p_i, it cannot divide it.

Combing the above facts, we can conclude that X! has first Z primes as its prime factors, (where Z is the number of primes less than or equal to X. Hence, the prefix sum). So, if Z < (Y + 1), it cannot divide it. For Z >= (Y + 1), the first (Y + 1) primes are also present in X!, hence it would necessarily divide it.

Here’s an alternate solution using Sprague Grundy Theorem

5 Likes

I believe the TLE was due to errors at their end somewhere, despite them telling us that there was no issue and at least two comments bringing up the problem were deleted.

I even issued this code which made no attempt to solve the solution, just tried taking the input, and it got TLE for the same test cases that you had issues with. See here: CodeChef: Practical coding for everyone

You shouldn’t be using endl to print a newline as it flushes the output also. Use the newline character as it has better performance.

2 Likes

Ever heard of FAST IO? There are 10^6 Test Cases dude. Using normal IO, I mean, cin and cout in CPP and input and print in python will definitely result in TLE. Scanner in Java will also result in TLE.

Not heard of “Fast IO” per se, but I had to use sys.stdin to take the input if that’s what you mean. This is the first time I’ve ever had any problem with being able to take input using input().

Yes, stdin and stdout classes are used in Python for Fast IO.

Try this Problem. This Problem changed my opinion on Input and Print Statements in Python. Now, I no longer use input and print statements in Python.
I wrote a Template that handles IO efficiently, that’s enough from now.

I think it’s a good idea in general for a Problem to require you to output a “hash” of results rather than having to output 10^6 of them - the latter approach leads to unnecessary headaches, and the former means you can get away with harder testcases for the same time limit :slight_smile:

This is the approach I took with MOVCOIN2 and MVCN2TST (though the time limits were still a little tight even after that :frowning: ).

4 Likes

Thanks for the heads up. Presumably, then, statements scanf and printf in C will also run into issues. What would I use instead of those if I were to use C more often?

No. I haven’t encountered any Issues due to Scanf and printf statements in C. Like, I mean, 98% of the times, these are enough.

If you strongly believe scanf and printf are resulting in TLE, you might want to use getchar_unlocked. I don’t recommend it anyways. As far as I believe and I understand, scanf and printf are more than enough.

If you want to learn more about Fast IO and would like to take inputs from me, you may create another thread.

1 Like

https://www.codechef.com/viewsolution/42627064
why i am getting tle to just reading input and printing it

Oh dear, I already mentioned the reason.

USE FAST IO @akshay_012.
One more, let’s not spam this thread for TLE issues. I would advise you to browse the Internet about optimising Input/Output. Self learning is always useful

This actually helps. What I understood by this statement is, instead of reading inputs one by one, computing the result and printing it one by one, read entire input (if possible) at once, store the input in an array ( best for Integers), compute the result for all of them, store the corresponding output in another array, finally dump this long output to stdout in one go.

Though it may look crappy, I feel it as a lot more better solution as stated by @ssjgz.

ok fine
https://www.codechef.com/viewsolution/42627387
what about this i have used FAST IO so many times but it seems it’s useless
it never work

Here’s the same solution, with minor modifications. I prefer for loop over while loop. Though I don’t understand why using while loop is less efficient when compared to for loop.

But never experimented with other stuff?
As I mentioned, I prefer for loop.

thk

Disagree.

First, it introduces an extra layer of complexity in the code. Even if the hash is as simple as the XOR of all results, it still has a different concept involved and messes with the actual problem logic. For example, one might get a WA due to computing incorrect XOR/hash. Imagine one’s surprise/frustration.

Second, it makes it extremely difficult to debug. Sure, I can print all values locally and check, but what if I need to tally my solution (after contest) to other contestants to get a failing test case. Compare the ease when you can see all the outputs vs you see just one integer representing the XOR of all numbers. How do you reverse engineer that?

Third, it increase problem statement length by explaining how we arrived at the sample output each time. There’s always gonna be people who are new to whatever hash you use, and you have to explain it everytime.

2 Likes