Help Needed - FCTREE

help
, ,
1

Can anyone help me to fix TLE for Subtask 3 for CodeChef: Practical coding for everyone from April LC 2020?

Here is my solution.
https://www.codechef.com/viewsolution/32013511

I posted my query in editorial comments section but did not get any response so far. Disappointed!!!

2

when you are working with Mo’s try using int arrays instead of maps and try not including extra logN factor since for Mo’s time limits are already too tight.

I didn’t went through your complete solution since it is too time consuming (going through someone’s code , specially if it us un-commented).

factors function in your code returns unordered map of prime factors.
size of which can be logN.
in the same function you are also factorizing integer every time this function is called

because of this an extra logN factor is added in the overall complexity.

try precomputing this instead of each time factorizing a number.

1 Like
3

Some tips to speedup:

  1. Change the block size from \sqrt{2*n} to (2*n)/\sqrt{q}
  2. Change all unordered maps to plain vectors
  3. Do not call factors functions each time, just precalculate in in a vector<vector>
  4. I believe the size of inverse array should be atleast 2e6

Also in Mo’s Algorithm, the ‘toggle’ functions gets called the most, so it should be highly optimized and in ‘toggle’ function, apart from calling the factors function, you are also unnecessarily copying an unordered_map. unordered_maps have never worked out for me, their average O(1) search seems useless to me.
You could also try hilbert ordering as in the editorial, which they claim to be faster than O(q\sqrt{n}) (or maybe has a low constant factor) but It didn’t work out for me for subtask 3, all the testcases TLEed.

4

Even though I am using unordered_map I actually using caching for the factors also. But does not help. Tried Hilbert order without any luck. I guess problem lies in different part of the solution. Not able to figure out. Feel free to modify the solution and try.

5

I am also using caching for all the factors. So no factor is calculated twice. Are you sure unordered_map is the problem here? I did not get your comment on extra logN factor. Can you please explain more?

6

Why it should be sqrt(2*n) instead of sqrt(n)?

7

Here n is the number of nodes, I forgot to mention :sweat_smile:.
Euler tour array will be 2*n in length, on which we are using Mo’s algorithm.

Also kindly see the 4th point too, initially I had left the size of inverse array as 1000 (by mistake), and many of my submissions showed TLE verdict rather than segmentation fault.
I know you are using caching, but still it does not change the access time of an unordered map and the fact that you are unnecessarily copying maps.

8

Can you explain the 4th point why I need 20x(max_size_n)?

9

You need inverses for the powers for the prime factors. It has no relation to the number of nodes but to the max value of A_i. So the max product for a query could go upto (10^{6})^{10^5} which is 10^{6*10^{5}} so the max power of a prime factor (which would be 2) could go upto log_2(10^{6*10^{5}}) which is around ~2*10^{6}.

1 Like
10

Thanks for the explanation. Yes my bad. That should be max_A.

11

Finally AC but it takes 6.82 sec.
https://www.codechef.com/viewsolution/32796266

I used 630 as Block Size and changed unordered_map to vector to store factors. Is there any other optimization I can do?

12

Done some optimizations. Better timing.
https://www.codechef.com/viewsolution/32814146