Getting TLE in SEACO even after doing Lazy Propogation. Help please.

general
, , ,
1

I made 4 segmented trees , 2 for commands(lazy and parent) and 2 for the array(lazy and parent). Now i processed the commands in reverse, and got the number of times the current query has to be executed from the command segment tree. If it was of type 1, i updated the array segment tree otherwise updated the query segment tree by that amount as said by meooow.

Here is my code. Someone help me in clearing the third subtask in python. I submitted the same code in c++ and got AC in one go.

1 Like
2

The reason you get TLE is the inherent slow nature of Python. However since you are following my solution, I can explain how my implementation is faster than yours.

  1. I am using an iterative segment tree instead of a recursive one. I have provided a couple of relevant links under your other question.
  2. I am not using lazy propagation. You could say I am using the lazy, but not the propagation. How does this work? We break up the range update into pieces and store them at the relevant nodes just like in lazy propagation. However there is no need to propagate them here. Instead, while querying on a point we can gather all pending updates on it on the path from the leaf to the root. Note that this trick works for only specific types of updates, so this is NOT a substitute for lazy propagation in general.

Feel free to ask if something is not clear!

UPDATE: About the segment tree usage-
Take a look at the picture below. Consider that as the sum segment tree. I have noted below each node what range it covers. At first all values are 0, so consider the empty cells as 0.
The first update is on [1…7] of value 5. Just like in lazy propagation, the range [0…7] is distributed over the segment tree and the value 5 stored on the correct nodes.
The next update is on [2…5] of value 3. Once again the correct nodes are found, and 3 is added to the currently stored values in those nodes.

alt text

Now suppose you want to query on any index, say 5. For the query, just travel the path from the root to the index and add up all the values you find. For index 5, the query result is 5+3 = 8, which is correct. Try the same for the other indices to check for yourself. It’s quite easy to see how it works, and it is definitely simpler than implementing lazy propagation :smiley:

1 Like
3

you could have used only 2 segment tree, one for 1-type query, and 2nd for 2-type query,
go through my


[1], earlier I was using 3 segment tree, but then I realized 2 would do the work.


  [1]: https://www.codechef.com/viewsolution/15266097
1 Like
4

1.Thanks for those links. Really helpful.
2.Could you explain it with a relevant example. I couldn’t spot what you tried explaining me. what are those specific updates?

i usually code in python and i see you too are also a big fan of that…but sometimes its slow nature as you said costs me…and am not to much familiar with STL(c++). So how do you deal with that? Would you recommend me to stick with python or learn alternatives?

5

To explain the updates it will be helpful to use a few illustrations, I’ll get to it later today. Regarding sticking to Python vs learning C++, it depends on where you’ll be doing the programming, but generally speaking it’s good to know C++. Beyond the 6-7th problem in a long challenge Python can become unreliable. However @phben often solves almost all problems using PyPy, so there’s that too.

6

could you write comments on your code if possible…am not much familiar to STL.

7

Yeah illustrations would be very helpful. BTW how do you decide after seeing the question to code on python or c++? I mean you could do in both, but how do you prioritize?

8

I generally choose it by difficulty… for the first few problems I use Python because it’s easier but for the harder ones performance becomes a concern so I switch to C++/Java.

9

That was impressive. A big Thanks! :slight_smile:

1 Like