MSTICK - Editorial

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

unable to figure out whats wrong with this?
http://www.codechef.com/viewsolution/3963394

What would the fault be in my solution?
http://www.codechef.com/viewsolution/4069045

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

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

2 Likes

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

2 Likes

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).

2 Likes

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’)

2 Likes

@ravi1krishna3 : yes I also think that its wrong there M’/2… wonder nobody noticed it…

@ravi1krishna3 Fixed.

@milhaus but there are N^2 ranges possible, which will make it O(N^2*logN).

1 Like

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

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

1 Like

Thanks, my pleasure :slight_smile: