MSTICK - Editorial

editorial
, , , ,
21

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…

22

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 : CodeChef: Practical coding for everyone

23

CodeChef: Practical coding for everyone Can view my sol here. Not getting where is the prob,getting correct answer for all test cases

24

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

25

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

26

I am trying to solve the problem matchsticks MSTICK Problem - CodeChef

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 CodeChef: Practical coding for everyone

27

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.

28

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

29

That was a really nice problem :wink:

2 Likes
30

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

2 Likes
31

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
32

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 Cartesian tree - Wikipedia.

33

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

34

I think the time for all the matches to burn out completely should be
m + max( (M-m)/2 , M’)

2 Likes
35

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

36

@ravi1krishna3 Fixed.

37

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

2 Likes
38

CodeChef: Practical coding for everyone. See this nice solution. It is AC without using any segment trees and some advanced technique :slight_smile:

39

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

1 Like
40

Thanks, my pleasure :slight_smile: