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.
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:-CodeChef: Practical coding for everyone
@taran_1407 or anyone who understands java please just look my code and can u tell why its
giving RE in Subtask1 and Subtask 2. I have commented the code and it will be easier to understand.