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 
This is the approach I took with MOVCOIN2 and MVCN2TST (though the time limits were still a little tight even after that 
).
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
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.
6 Likes
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.
1 Like