Getting TLE for TREDIFF

I have implemented the code for TREDIFF as explained in the POST CODECHEF DISCUSSION by @rajarshi_basu

Link to the code : Tree Difference - May Lunchtime codechef -

I am getting TLE for the second task.

What is wrong in my code? Please tell me ? I was unable to figure out.

@ssjgz Why is it getting TLE

I can’t see anything that would make it O(N \times Q) or anything like that, so I suspect it’s only just timing out by a small amount, most likely due to your unnecessary use of a std::set.

(I have a testcase here that takes your solution 3.83 seconds on my laptop, but my laptop is slower than Codechef’s servers, so I’m not sure if that counts … )

1 Like

Without using sets there may be a chance of putting duplicate values which eventually gives 0 everytime. Therefore to avoid that i am using set. set operations usually takes O(1) right?

No, set::find and set::insert take O(\text{size of set}). They also have a fairly high constant factor.

Granted, my_set in this case won’t contain more than 100 (a constant) elements, but it’s still slowing things down.

1 Like

How can i optimize this code to make it work. I tried to implement optimal one, but i failed :pensive:

Think it through - I’ve already suggested one think that is probably causing it to TLE! :slight_smile:

A hint, to get you on the right track - what is my_set doing? Is there a way of doing it without using something as slow and expensive as a std::set? The Editorial solution doesn’t use one!

1 Like

I will try to use a bool array

Here’s a testcase to practice on :slight_smile:

1 Like

Do you write a program to generate these kind of test cases?

Yes :slight_smile:

1 Like

Does any ide accepts this large test case?

I don’t know, sorry - I don’t use an IDE for CP.

1 Like

How can i do then? Codechef is not accepting this one

Compile and run it locally.

1 Like