need help in pointing out my mistake>

problem link:https://www.codechef.com/problems/MSTICK
solution link:https://www.codechef.com/viewsolution/16520062

It is a basic segment tree problem with an insight.

Click to view

First thing, calculate min (L,R), This is the time fire reached joint end.

Calculate max((0, L-1), (R+1, N-1)). This is the time fire will take from joint end to reach tip of matchsticks which were not ignited.

calculate ceil( (max(L,R) - min(L,R))/2). This is the time for all matchsticks within range L to R to be ignited completely, after fire reaching joint end.

Now, answer will be min(L+R) + max( max(0, L-1), max(R+1, N-1), ceil( (max(L,R) - min(L,R))/2)).

Now, Implementing it is a simple implementation of Segment tree.

Its simple. Use double not float because you need precision for values as large as {2}*{10}^{8}.

See this TC-

Input
5
100000000 100000000 100000000 100000000 99999999
1
2 4
Your Output
200000000.0
Correct Output
199999999.0

Determining what data type to use is the most fundamental concept which requires 100% accuracy. Be careful next time.

Also, next time, please give 2 minutes into indenting your code or adding proper comments. Its really painful for eyes to see an un-indented and uncommented code. Please think of the person going through your code to help you.

2 Likes

this is exactly what I have done.
it would be helpful if you could point out the mistake in my code

i guess you should use ceil function for ceil( (max(L,R) - min(L,R))/2)

Also, refer this implementation of Segment tree for min-max queries

but i did max((max(l,r)+min(l,r))/2,min(l,r)+max( max(0, L-1), max(R+1, N-1)))
which is basically the same thing and hence does not require ceil function

Wait…

I’m solving it myself…

it would be nice if u could point out error in my code,instead of solving it your self:)

Your segment tree is working fine…

Can’t figure out what’s wrong with your code… :frowning:

My code with same approach gives AC

https://www.codechef.com/viewsolution/16521589

thanks a lot!!
And I definitely will try to indend my code from next time…

thanks for your help…
found the solution to my problem

Thank you dear :slight_smile:

No problem. Although @vijju123 is the one to be thanked.