MSTICK - Editorial

editorial
, , , ,
3

nice to learn such wonderful ways… thank you…

2 Likes
4

I think there is a mistake in the above formula…it should be m + max( (M-m)/2 , M’ ) and not m + max( (M-m)/2 , M’/2 ) because for the matchsticks which are outside the boundary ‘l’ and ‘r’ it wont be burnt at both the ends…so M’ shouldnt be divided by 2…isnt it?

5

One of the best problems i’ve solved so far.
Being a newbie to codechef,this was my first shot at segment trees.
I’m really thankful to the mkagenius for giving such a wonderful oppurtunity to learn new data-structures.

1 Like
6

2 questions if someone can help me… 1—i was using segmented trees for the same problem. making a vector(just to store the burning time) and passing it through main gave me TLEs while same solution with only change being, i used a global array instead and it passed. why is it so? i agree vectors and STLs can be a bit slower but i wasn’t using any inbuilt function or anything just a vector to array and AC… here are the links:
TLE and
AC
2–Also, using segemnt tree i had to make 2 trees obviously one for max and one for min, is there a way of doing it using only one tree?
thanks in advance…
PS- great problem. loved it thanks! :slight_smile:

4 Likes
7

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

2 Likes
8

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

1 Like
9

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 …

10

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
11

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

12

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

4 Likes
13

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.

14

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

15

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

16

Hey , I followed the first approach (finds range min query in time O(rootN)) . Upon submitting the code , I am getting Runtime Error. CodeChef: Practical coding for everyone

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.

17

I have implemented the segment tree and correct approach , it is working for basic test cases but giving WA can somebody see CodeChef: Practical coding for everyone

18

i m getting WA for the question MSTICK Problem - CodeChef but not able to figure out why… kindly help… my solution is

19

I get WA,can anyone tell me what am I doing wrong?
My submission- CodeChef: Practical coding for everyone

20

Hey Though I have test a lot of test cases and have considered the double part still the WA…:frowning:
heres my sol: CodeChef: Practical coding for everyone .plz help…:frowning:

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