FCTRE - Editorial

I did this in a slightly different way and passed in 2.32 seconds.

Note that for a number A \le 10^6 , there can be no more than one prime factor larger than 10^3. If there is a prime factor of any A_i which is larger than 10^3, I divided it by that factor. Now we are sure that all A_i 's consist of prime factors less than 10^3. There are only 168 such primes. For each of these, I calculate sum on path using LCA. Note that you need to calculate LCA only once and after that you need to calculate sum on path for every prime.

Okay, so we are done with all primes less than 10^3.

For primes less than 10^3, we will simply do Mo’s algorithm as in the editorial. But now, the add remove function is just O(1) as you just need to maintain count and not the complete factorization of the number.

So this ran in O(N\sqrt N + 168*N + NlogN) (with a good block size obviously!)

PS: It took me a huge number of submissions to get this AC. I was doing one mistake. Maybe some of you made the same mistake. I precomputed (L/BLOCK) for the query comparator and initialized only N indices of that array. I should have initialized 2*N of them. It took me about 70-80 submissions to figure this out as the verdict was always TLE. Affecting the ordering only affects the runtime, not the correctness of your code.

4 Likes

I did use LCA and segtree but only managed to get 10 point, I suppose using LCA with sparse table is more efficient as it get rid of log N factor?

Great approach. No wonder you are in the fastest 30 submissions. Ig I was quite lucky to get it working under 20 submissions with inline add/del, optimized comparator, const block size, and most importantly limiting the mod operator (I use modular arithmetic template). My solution operates in 6.8sec.

2 Likes

Thanks a lot : )
Yeah actually I had never really implemented Mo before this. Even this is mostly the same as one I saw somewhere. But you see, this error is subtle, the reason being: I always thought that my code is slow (and never thought that sorting could cause Mo to get this slow) , when it was actually not. When I first submitted I was 100% sure of a WA or an AC. TLE on last case was wild. But then I thought I am overestimating performance maybe. And it took me a whole day to get AC and a few hours of the next day to understand that why this array was causing an issue and why writing l/BLOCK passed.

2 Likes

Just asking, how did you find top 30 though :sweat_smile:


this is major problem in this question.

1 Like

There was certainly some issue with the judge for this problem. The exact same code when submitted at different times gave running times as 4.75 and 6.58 during the contest. That’s a huge difference.

actually I always go through top 25 submissions just to learn from others code. and your’s runs in 2.32 so I rechecked the submissions and yours was just below it.

Yeah I mean where to find these top 25?

will u please share the link of those codes. and mention in this section–>

I am really sorry. Actually I made more than 70-80 submissions, don’t even know. I will really not be able to find that out.

Basically the problem page has “Successfull Submissions” section (on right) where solutions are in increasing order of time taken. Each page has like 12 submissions.

Ah I get it. I found it. It shows the first AC submission. It’s the one with 3.33 seconds. Thanks a lot for the info. Gonna use it later : )

1 Like

if you use sparse table u will get memory space limit excceed

I instead got tle.
Got partial correct .

Blocksize = 550, AC with 2.94s Here
Blocksize = 700, AC with 2.83s Here
Blocksize = 630, TLE Here

After the contest, I re-submitted the code with blocksize 630 and it gave AC with 3.29s Here

make use of lca along with MO algorithm it will take sqrt(n)*logA time which is fast enough to pass the above constraints.

Notice that for second subtask, N \le1000. So you can precompute the answer for every (u, v) pair beforehand store them.
For this, we can use DFS once from every vertex, assuming it as u. Now in a single DFS, answer for every corresponding v can be found.
Answering every query thus becomes O(1).
For implementation details you can refer this

I applied all the above things but still got tle on subtask 3. here is my code, can anybody tell me what’s the problem . Please take a look at it.
https://www.codechef.com/viewsolution/31502577

Hey, Can anyone please tell me, Why i am getting TLE in even first subtask.
Since, I think the overall complexity will satisfy the constrains of subtask1.

Solution Link