TLE in #FLIPCOIN

Repeatedly I’m getting TLE in FLIPCOIN, please someone suggest an optimized way to achieve correct answer.

Problem statement: - FLIPCOIN Problem - CodeChef
My solution : - CodeChef: Practical coding for everyone

Any suggestion optimizing the solution is appreciated

I see you’re trying to solve by traversing the array for each and every query. This is very straightforward approach and yeah, you have to optimize it.
This problem requires the use of the data structure segment tree. (In general, if there are multiple queries of finding some value or updating some values in array, most of the times it can be solved by segment tree.)

Also, it requires updating a range of values, so you’ll need to know about Lazy Propagation too.

Okay, but to get the result(may it be an update or to display ) of each query each query needs to be traversed…am I right?
Still I’ll work with segment tree and lazy propagation… I’ll get to learn something new, so thanks @yashkmr99

No, the segment tree is built such that each node contains the result of some range. So, for each query, you’ll have to combine the values of some nodes to get the result.

There is another algorithm known as Mo’s Algorithm, which is based on traversing (and it is easier). But this algorithm only works when there is no update query (the array remains unchanged throughout). You might also check that out.

For this problem, you’ll need Segment-tree.

Thank you so much, I’ll surely go through these concepts. You’ve really been helpful…
I can ask again here if I get stuck somewhere…is that okay with you @yashkmr99 ?

Yeah, sure.

1 Like