MSTICK - Editorial

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

2 Likes

Segment trees need way too much memory to be allocated. Check out Sparse tables instead here

1 Like

Hi the segment trees section in the top coder tutorial only explains how to initialise the tree n query for a minimum in a given interval … could someone pls spare few mins explaining wat changes must be made to that algorithm to fetch the maximum in the given interval … It would be really very helpful … apologies if its a silly question …

hi mkagenious. I have tried and tried but getting a wrong ans. I have also looked at others solutions, but cant find any faults in mine. Could you please help me? My submission ID : 2172602.

1 Like

please some one help me in this code…http://www.codechef.com/viewsolution/2172202...giving wrong answer…cross checked many times… :frowning:

Wrote the code using RMQ. Can anybody guess where did I go wrong ?

4 Likes

I am solving this problem in O(Qroot(N)) but getting WA. I dont know where the code is failing,please check it once.

here is Ideone the link.

@mkagenius I again changed the code but getting WA :frowning: please help me :frowning: my solution id is :-2183210

I implemented a Python solution for this problem and it is as fast as the few Python AC ones but I got TLE. Can someone spot the issue ? http://www.codechef.com/viewsolution/2188068

Hey , I followed the first approach (finds range min query in time O(rootN)) . Upon submitting the code , I am getting Runtime Error. http://www.codechef.com/viewsolution/2185571

Total Memory Limit for this 50000 bytes.I declared two arrays of size 10000 each. So , it takes 80000 bytes [2*40000 bytes]. Is this the reason for the error ?

But, I have seen solutions using two arrays getting accepted.

I have implemented the segment tree and correct approach , it is working for basic test cases but giving WA can somebody see http://www.codechef.com/viewsolution/2276619

i m getting WA for the question http://www.codechef.com/problems/MSTICK but not able to figure out why… kindly help… my solution is

I get WA,can anyone tell me what am I doing wrong?
My submission- http://www.codechef.com/viewsolution/3339304

Hey Though I have test a lot of test cases and have considered the double part still the WA…:frowning:
heres my sol: http://www.codechef.com/viewsolution/3655905 .plz help…:frowning:

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