CORTREE Video Solution

Official editorial: CORTREE - Editorial
Link: https://www.youtube.com/watch?v=DBABfHdS3B8

3 Likes

can someone help in optimizing my solution /give some tips to avoid such tle’s in future
https://www.codechef.com/viewsolution/29990403
it uses the same idea as the editorials but is getting tle even on the small subtask.

@ssjgz @admin @tmwilliamlin

One thing I noticed is that you process the vector back from the front, but since we restore operations in reverse it should be from the back.
I don’t know if this causes TLE, though.

1 Like

tried it in the other way also.sadly still tle even on subtask 1 @tmwilliamlin

No offence,but before asking debugging questions to community you should test it on random test cases and see why it’s getting tle.also you should try to change seg tree implementation,use from any good source, and then try to figure what is the root cause, seg tree or something other.

well the seg tree is fine with right complexity and implementation
its just that the solution of this problem is nlogn^2 which requires lot of constant optimizations to pass in the tight time limit. also I debugged for a lot of time and couldn’t find anything so posted it here and asked for help.you can see how many submissions I made for this problem

1 Like

if it doesn’t even pass subtask 1 then it’s not a constant optimization issue

in my opinion also its a problem of constant optimization. because i have used your same approach then also it is getting TLE.
MY Submission link : https://www.codechef.com/viewsolution/30015560
please look into this matter sir.
@tmwilliamlin

1 Like

This is obviously not a constant optimization issue. This algorithm is nowhere near O(n^2), so passing n<=5000 shouldn’t be a problem. You probably have a bug in your implementation.

This is not FFT, this is just segtree constant. 3e6 is very fast

1 Like

But sir my implementation is almost similar to you. just only passing the parameter in function is changed. pls check it once again sir. :pray::pray:

1 Like

@kshitij_789
you were building segment tree in a wrong way i edited you code little bit and got AC.
https://www.codechef.com/submit/complete/30021397

3 Likes

https://www.codechef.com/viewsolution/30021397

Yea 3e6 operations is 0.01s, nowhere near TLE lol.

2 Likes

Sir, please help me also… :sweat_smile:

You have the same problem.

1 Like

@agrawal117
tmwilliamlin is correct you are also building segment tree in wrong way.

1 Like

Thank u so much. i found my mistake.
@tmwilliamlin @srinivas1999

2 Likes