FCTRE - Editorial

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

Without Blocks, you can get AC using Hilbert curve to sort the queries.

1 Like

I guess using pointer might be the issue,pointers are pretty slow,also you will still get tle,you need block optimization or better sorting order.

1 Like

SELF PROMOTION 100

I have used gilbert Order to sort queries but it was not enough to pass all testcases.
None of the solution passed all subtask in python3 and pypy3 so was the timelimit correct for python codes?
My solution link:-https://www.codechef.com/viewsolution/31846147