MSTICK - Editorial

editorial
, , , ,
61

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 :slight_smile:

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

62

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.

63

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