Can anyone please find the error.The code is working on all test cases I could find,but could not locate the error,getting WA.

Plz Help…

Hey I have used 2 segment trees for implementation. But still, I am getting wrong answer. Can’t figure out why. Could anyone please help me out? Solution : http://www.codechef.com/viewsolution/3792862

http://www.codechef.com/viewsolution/3902702 Can view my sol here. Not getting where is the prob,getting correct answer for all test cases

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

I used segment tree data structure still I get TLE with a complexity O(2N + Q4*log(N))

where O(2N) for building 2 segment trees and O(4Q*log(N)) for running 4 queries on the segment tree for each query Q.

Can somebody please correct me if I am wrong about the complexity of my algorithm or help me find out why do I get TLE ?

I would appreciate it, thanks

Here is my solution http://www.codechef.com/viewsolution/4170573

The below line, seems to give errors.

```
f=b;
f+=(a*(1.0)-b)/2;
```

While,

```
f=b;
f+=a;
f/=2;
```

gives, AC. I am perplexed, what is causing the error ?

AC Solution and WA Solution.

Can anyone find error in my code?It’s working fine for the given test cases.I have made two segment tree one for minimum range query and another for maximum range query.http://ideone.com/EvLByN is giving me WA

That was a really nice problem

one of the best questions I have solved so far! kudos to the problem setter

Using a segment tree, you can find the min/max in a range in O(logN). As there are Q queries, the complexity is O(QlogN).

Keeping a global maxima and minima (with indexes) would further improve the solution… especially the maxima… since that will be one of the three maxima for sure… and if it lies outside the range of selected ones… then you dont need to compute any maxima

m + max( (M-m)/2 , M’/2 )

if there is M’ = global maxima and outside the selected range=> [0,L]&[R,n]

=> m+M’/2

else

as above

also another link http://en.wikipedia.org/wiki/Cartesian_tree.

You precompute minima and maxima for various ranges in O(N*logN) and then answer all the queries in O(1).

I think the time for all the matches to burn out completely should be

m + max( (M-m)/2 , M’)

http://ww2.codechef.com/viewsolution/2106785. See this nice solution. It is AC without using any segment trees and some advanced technique

Thanks. I did not expect so many people will like it.

Thanks, my pleasure