Sorry, what should have been fixed in the contest? Your wrong solution, or what? Obviously, if you received Wrong Answer verdict, this means that your code DO NOT work on each test case.
Maybe you guys should have tested on python as well beforehand as what else could have been done as it is a Wrong answer because of python error not ours.
Well, at first there are solutions in python which got AC. At second, as far as I know nobody guarantees that each problem must be solvable in python at all.
2 Likes
sqrt is not precise enough. I was getting WA, then i wrote a binary search to get the floor of the square root. But that was giving TLE, finally I tried sqrtl and that passed
Also this is your problem, not anybody else mistake, that you don’t know/understand how does your code work, and why it can be incorrect.
1 Like
For a big contest like this. and problem related to BigIntegers. I think it should be solved. as most people fails to understand the % MOD part.
Anyways it was a great contest at last I did get AC.
why are you initializing ans=n%mod in the main?
if n is a perfect power it would have already been present in some d[i] already.
My solution did not involve the Inclusion and Exclusion:
- Choose M=\lceil{N^{\frac13}}\rceil . For all x\leq M, sum up the contribution of all powers of x. In order to avoid overcounting, keep a track of all numbers \leq M which have already been taken care of beforehand(as a power of some smaller x). This way, one can never count any power more than once. Also, do NOT add the contribution of even powers which are more M^2.
2)Now note that for x>M, only x^2 can contribute to the sum as x^3>M^3>N. Also, the square of such an x is greater than M^2, and we have already excluded such even powers in 1),hence we can directly sum them up with the interval trick mentioned by @taran_1407.
For both the steps, the running time can be computed to be O(N^{\frac13}).
Is there no LaTeX support for replies?
There \ is
Just put $math here$
2 Likes
My bad, there was a typo in there, thanks!
Hii @bohdan @taran_1407 Can one of you help me .Why my code is suffering from a tle . I used set stl to remember perfect powers from cubes and checked if it is a perfect square or not so as to not repeat using same perfect power.Didnot use inclusion exclusion principle but only traversed over prime powers. Tried hard but could not optimise it any further. My code is also of around the same complexity O(n^1/3) maybe with a log (n) overhead but unable to pass. Code link : CodeChef: Practical coding for everyone
I pre-computed the square-free perfect powers starting from cubes which are around 80k till 10^18. For squares I used two approaches,
- when the square-root is greater than 10^6, let’s say the sqrt is x than the quotient is N / (x * x) and the contribution becomes x * x * quotient. but we can’t keep reducing the sqrt, so I reduced the quotient and found the range of squares which gives this quotient. so the sqrt which gives higher quotient is prev = sqrt(N / (q + 1)), now we just calculate the sum of squares from prev + 1 to sqrt (N/ q).
- when the square root is not greater than 10^6, I calculate the contribution for each square.
- I tried to make my code readable and can be found code and it is the fasted java code taking 1.32 seconds.
- and yes, the Math.sqrt function doesn’t give the correct integer value when the number is large and very close to square, one example: for (10^18 - 1) it will give 10^9 and that is precision error I had to take care.
1 Like
yes, same thing I also faced in java, when the number is just less than big square. I had to take care that precision error and it took some time. for example the sqrt for (10^18 - 1) was giving 10^9 as integer value and it was giving WA. you can see my solution here
Can any one tell me the problem with my code. I am only getting 60 points in it.
This is my code.
https://www.codechef.com/viewsolution/31830398
1.) I have first found the contribution of all powers greater than 2
2.) Then i have found the contribution of power 2 till 10^6 itterations i.e value = 10^12.
3.) Then i have found the remaining ans for power 2 by - the contribution of any value above 10^6 square cannot be greater that 10^6 as the value is atmost 10^18, so just find the set of values or bunch of continuous values with contribution 1,2,3…10^6-1 and add them using sum of squares formula and multiply them with the corresponding contributions.
Help Please, i was able to get 60 points only even after trying all the optimizations and i think i have done it in similar way to the editorial. spent days for this problem, please help me how can i optimize it more?
https://www.codechef.com/viewsolution/31595523
here is my accepted code you can check how i deal with square root to get rid of wa in last sub task hope it helps
link::CodeChef: Practical coding for everyone
I understood the code but my code here has T*sqrt(N)logN complexity ,still it got time limit exceeded on the third subtask(for N<10^12).Can anyone help me here ?
As far i know ,you have to reduce your solution O(T*cbrt(n)) to get A.C.
Getting TLE for the last two subtasks, did exactly the same thing as explained in editorial.
Can anyone please point out the mistake?
My submisstion : CodeChef: Practical coding for everyone
In my machine, I am instantly getting output for n as large as 1e18.