Matchsticks Segment tree implementation and TLE

general
, , ,
1

I am trying to solve this problem : http://www.codechef.com/problems/MSTICK/

I already posted on the Editorial thread relative to the MSTICK problem but no one answered.

Here is my solution to this problem : http://www.codechef.com/viewsolution/4172545

I don’t know what’s wrong with it, it gets TLE.
I implemented the segment tree data structure and I “think” the complexity of my algorithm is O(2N + 4Q*log(N)) which comes as follow :

O(2N) for building 2 segment trees, one to find the minimum and another to find the maximum.

O(4Qlog(N)) since I run 4 Range_Min(Max)_querys for each query Q.

Everything seems to be working but I still don"t understand why I am getting TLE.

If anyone can help me please?

2

Hi ! The problem is you are passing a vector by value in your segment tree build function. So, every time a call is made, a copy of that vector is created which is O(size of vector). So, either make the vector global or pass it by reference (in your code by using “tl & A” in place of “tl A”). Hope it helps. :slight_smile:

1 Like
3

Hi ! Thank you I can feel that my program is running faster. But now there is another problem. I am getting a WA…