CORTREE Video Solution

editorial
,
1

Official editorial: CORTREE - Editorial
Link: CORTREE Solution - CodeChef February Lunchtime 2020 - YouTube

3 Likes
3

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

4

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
5

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

6

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.

7

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
8

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

9

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 : CodeChef: Practical coding for everyone
please look into this matter sir.
@tmwilliamlin

1 Like
10

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.

12

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

1 Like
13

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
14

@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
15

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

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

2 Likes
16

Sir, please help me also… :sweat_smile:

17

You have the same problem.

1 Like
18

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

1 Like
19

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

2 Likes