problem link
can any one help me with this problem … i am not able to understand the editorial… problem description is short and simple
I hope you have understood that you just need to simulate the process given in the problem. For that, you need to find the longest contiguous segment, and that too the leftmost. So what do you need to store to quickly find that segment?
You can use a set which stores {-length, start_idx}. So the first element in this set will always be the longest, leftmost segment. Now you can just remove it. BUT, since after removing this segment, the two segments on the left and the right of this might merge (if they are equal), you need to manage that case too!
So, how can you quickly find the left and the right segments of this guy? You can use another set, which stores elements as {start_index, length}. Using this set, you can find the segment which starts before your current segment, and similarly the one starting after. Then if they have equal value, you can just remove both of them and add a combined segment with total length as the sum of their individual lengths.
There is some casework involved, like, when this segment is in the starting, or at the end, and other things that you’ll have to take care of.
I have a messy Implementation, which you can check for reference.
Anyway, this problem was a bit irritating to code, but I hope the concept is simple enough!!
1 Like
thanks for help