hiie bruh…naku ehh solution artham kale can u pls help me out? please?
@binny_0123 , Here is my brief explanation,
- As per the question, we can change the number we have , let’s call it Z to Z - D , with the condition that D <= Z and D is divisible by atmost Y number of distinct primes. [ We can also restate the Statement as D cannot have more than Y distinct prime factors ]
-
Now , let’s consider a number which is product of first Y+1 primes , let’s call it A ( 2 is considered as first prime here )
Example , when Y=1 , A = 2*3 , when Y = 4 , A = 2*3*5*7*11
-
why do we care about A ?? because observe this , if we have a number which was multiple of A ( Z = K * A ) , then after performing the subtraction operation with any valid D , we always end up with a number which was not a multiple of A.
Why was the above statement true ??
Well if Z is a multiple of A and Z-D is also a multiple of A that imples D is a multiple of A , but A contains Y+1 Distinct Prime factors , so any multiple of A contains atleast Y+1 Prime factors , so any muliple of A was divisible by atleast Y+1 primes , which makes the D an invalid choice.
if D was not a multiple of A then , Z-D is not a multiple of A (obviously) [ because if we divide Z-D with A , we get (Z - D)/A = Z/A - D/A = K - D/A , where K is some integer and D/A is not going to be a integer]
- Another observation , Any number less than A is going to be a valid choice of D and any multiple of A is going to be an invalid choice of D.
Why was the above statement true ??
Because any number less than A cannot contain more than Y distinct primes as factors
[ if it was not obvious , let’s think about smallest integer which has Y+1 distinct prime factors , let’s it be B = (P1)^e1 * (P2)^e2 * … (P+1y)^ey+1 , with the same primes , we will get the smallest numbers when the exponents are 1. so B = p1 * p2 * … * py+1 , now we will get the smallest number when we choose the smallest prime which we didn’t previously choosen . like when Y = 3 , we can let B = 2 * 3 * 5 * 7 which was same as A , so A is the smallest integer which has Y+1 distinct primes as it’s factors. which implies any number less than A can not have more than Y primes ]
- Now we can discuss about optimal strategy , let’s consider two cases
-
Case 1 :- Initially given number is not a multiple of A ( Z = K * A + R)
-
Now if the number is less than A , first player can choose the D to be Z , which was valid and first player wins.
-
If the number is greater than A , ( Z > A ) , which means , Z = K * A + R , where K is some integer and R is remainder (when we divide the Z with A) and R < A and R > 0 , Now we can choose the R as our D , which was a valid choice since R < A
-
Now the second player will get ( Z - R ) = K * A , which was a multiple of A , he can not make it Zero since inorder to make ( Z - R ) zero he has to choose D as (Z - R) , but that was not a valid choice since ( Z - R ) is multiple of A.
-
Which means , he can not win in his turn and no matter which D he chooses first player alwasy get a number which was not a multiple of A.
-
If this number is less than A , first player can make it zero or he will again make the number a multiple of A for the second person.
-
Eventually the number should go below A and in that turn A will Win.
-
Case 2 :- Initially given number is a multiple of A ( Z = K * A)
-
Now first player can not make the number 0 , and no matter what the first player chooses the second player will always get a number which was not a multiple of A , and he follows the above strategy making sure the first player can never win and eventually winning the game.
- So now the problem is reduced to find wheather the given intial number is divisible by A or Not , but since the given number is factorial of some number (X) we can find wheather X! is divisible by A or not by simply checking , is X >= ( Y+1 th prime) [ counting with 2 as first prime ]
- If we take any number less than a prime p , then that number cannot contain P as a factor.
- So , all numbers from 1 upto Y+1 th prime didn’t contain Y+1 th prime as it’s factors.
- So , product of all numbers upto Y+1 th prime (Not including Y+1 th prime) can not also contain Y+1 th prime
- Which implies , it can not be divisible by A so if X < (Y+1 th prime) then X! is not going to be a multiple of A.
- If X >= ( Y+1 th prime ) , then it contain Y+1 th prime and also all primes before that , which imples that if X >= (Y+1 th prime) then X! is a multiple of A.
Hope this is helpfull.
Try using Fast I/O
can you explain what happens in the situation when x=6 (6!) and y=2;using the above divisibility rules you said above? why would divyam win in this case?
I understood that when x! has no of prime <= y chef will definetly win but why would divyam win if no of primes > y?
- In this case the given initial number is 6! = 6 * 5 * 4 * 3 * 2 * 1 or 6! = (3 * 2) * 5 * (2 * 2 ) * 3 * 2.
- Since Y is 2 , let A = product of smallest Y+1 primes. i.e A = 2 * 3 * 5.
- Now , the first player , chef can not make 6! = 720 zeros because it was a multiple of A [since inorder to make 720 into 0 , D should be 720 which contains more than 3 distinct primes make the D as 720 an invalid choice.]
- See the 4 th point to understand the optimal strategy
- For example if chef chooses D as 1 , then the Divyam will get 719 , so the remainder is 29 , one example of optimal game is
1. Chef 720 -> 720 - 1 -> 719 2. Divyam 719 -> 719 -29 - > 690 3. Chef 690-> 690 - 625 -> 65 4. Divyam 65 -> 65 - 5 - > 60 5. Chef 60 -> 60 - 50 -> 10 6. Divyam 10 -> 10 - 10 - > 0
So , finally Divyam , wins. If you don’t understand the optimal strategy read the entire post once again slowly , u will understand it.
Isn’t it like: Chef can only win on the first chance otherwise he won’t. And that winning chance will only occur if P(X) (number of primes till X) is less than equal to Y. That’s what I based my solution on.
I believe this is caused because you’re using std::endl, which is really slow, instead you should use “\n”.
Could you prove it why is it working?
Thanku very much got it completely…
My conclusion is when chef gets the number exactly divisible by A then whatever the D he subtracts divyam will always try to him again a divisible state untill number becomes less than A …Hence divyam wins ultimately…
Thnak u very much for that example
Anyone have done this question in java.
Thanks a lot for the tutorial. I solved the question and have attached the code here. I figured X! is “divisible” if X is greater than or equal to (y+1)th prime and not divisible otherwise. Can someone tell me why this is wrong? Or am I missing a corner case? Thanks in advance
#include "bits/stdc++.h"
#define ll long long
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll primes[(int)1e6+10] = {0};
vector <ll> prime;
for(int i = 2 ; i < 1e6 + 10 ; i++)
{
if(primes[i] == 0)
{
for(int j = 2 ; i*j < 1e6 + 10 ; j++)
primes[i*j] = 1;
prime.push_back(i);
}
}
ll tt;
cin >> tt;
for (int pp = 0; pp < tt; pp++)
{
ll x, y;
cin >> x >> y;
if(x < prime[y])
cout << "Chef\n";
else
cout << "Divyam\n";
}
return 0;
}
Even I am getting TLE on Submission !!
But when I “Run” it with max constraints…its well within the TL !!
Can you share the template? I’ve faced TLE in python but got AC in CPP for the same algo.
Yeah, Sure. Here you go.
from sys import stdin, stdout, stderr
def solve():
pass
def main():
io = IO() # Line 7: IO Object Created here
t = io.Int() # Calling Int() method to read a single Integer.
for test in range(t):
solve()
class IO:
def next(self): # Reads 1 entire line from stdin.
return stdin.readline().strip() # strip(): Removes whitespace and newline characters at beginning and end
def nextLine(self): # Same as next() method
return self.next()
def String(self): # Same as next() method
return self.next()
def nextStrings(self): # Returns list of strings from 1 line, split at spaces, from stdin
return list(map(str,self.next().split()))
def nextInt(self): # Returns single Integer. Make sure there is only one Integer in the line to be read.
return int(self.next())
def Int(self): # Same as nextInt() method
return self.nextInt()
def nextFloat(self): # Returns single Float.
return float(self.next())
def Float(self): # Same as nextFloat()
return self.nextFloat()
def nextList(self): # Returns list of Integers (usually used to scan array of Integers).
return list(map(int,self.next().split()))
def List(self): # Same as nextList() method
return self.nextList()
def nextTuple(self): # Returns tuple of Integers (usually used to scan pair of integers or more)
return tuple(map(int,self.next().split()))
def Tuple(self): # Same as nextTuple() method
return self.nextTuple()
def debug(self,*obj,sep=" ",end="\n"): # Writes an object to stderr stream. Useful to debug your variables.
# Special since it will not interfere with stdout, so even if you forget to remove, you'll get AC
string = sep.join([str(item) for item in obj])+end
stderr.write(string)
def print(self,*obj,sep=" ",end='\n'): # Writes an object to stdout stream.
string = sep.join([str(item) for item in obj])+end
stdout.write(string)
def write(self,*obj,sep=" ",end="\n"): # Same as print() method
self.print(*obj,sep=sep,end=end)
def yes(self): # You can ignore the following methods, I added them recently to my template
self.write("yes")
def Yes(self):
self.write("Yes")
def YES(self):
self.write("YES")
def no(self):
self.write("no")
def No(self):
self.write("No")
def NO(self):
self.write("NO")
main()
# Remember to call main() method after you define all classes and methods in your code.
A brief description of this snippet.
- IO is a user defined class (defined by me).
- In order to use the methods, you have to create an object.
- There are three major methods I defined. These include next(), Int(), List() methods. These are the ones that are mostly used. Others are also used, but not frequently.
- I provided description for each method in comments, feel free to ask if you don’t understand anything.
I would also like to provide you the link of my Repository, where I put my templates. I keep updating them.
Thanks a lot.
Initiate
b[0] = b[1] = 0;
And there you go
Nice problem. Thanks for the editorial😊