PROBLEM LINKSDIFFICULTYSIMPLE PREREQUISITESRange Minimum Query, Simple Math PROBLEMYou are given N matchsticks arranged in a straight line, with their rear ends touching each other. You are also given the rate of burn for every matchstick (possibly same) in number of seconds it takes to burn it out. If a matchstick is lit from both ends, it burns out twice as fast  taking half as much time. Answer several queries of the following type efficiently All the matchsticks in the range L to R, inclusive are lit from their front ends simultaneously. Find how much time it takes for all the matchsticks to burn out. QUICK EXPLANATIONFor each query, the operation performed plays out in the following way
We can find the time taken in all the steps above using only the following pieces of information for the segment L to R
EXPLANATIONFor a given range L to R
The time taken by each of the steps in the scenario described above is as follows
Thus, the time taken for all the matches to burn out completely is m + max( (Mm)/2 , M' ) It remains to find efficiently the minimum time some matchstick will take in a range, and the maximum time some matchstick will take in a range. Such queries can be answered in O(N log N) time by using segment trees. Refer to this topcoder tutorial for a wonderful writeup with code samples on how to get about writing a segment tree. The topcoder tutorial also describes a O(N sqrt(N)) approach as well which will also work within the time limits for this problem. Two segment trees must be constructed. One to answer queries of the type "minimum in a range", that returns the time it takes for the fastest burning matchstick to burn out. Another to answer queries of the type "maximum in a range" to find M and M' as defined above. Note that M' will itself be the maxmimum of two ranges, 1 to L1 and R+1 to N respectively. A lot of solutions were stuck in the caveat that it is required to always print the answer in a single decimal place. Note how the answer will either be integer, or contain a single decimal digit (5). In case the answer is integer, it is required to print a trailing decimal followed by 0. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONApproach  finds range min query in time O(rootN)  solution. Approach  finds range min query using segment trees in O(logN)  solution.
This question is marked "community wiki".
asked 14 May '13, 15:19
showing 5 of 7
show all

2 questions if someone can help me... 1i 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 2Also, 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! :) answered 15 May '13, 13:04
1
p.S. Happy to know that you liked the problem :)
(15 May '13, 23:39)
2
@mkagenius ok got it.. using stuct yeah that had to be obvious! :P
(16 May '13, 18:40)
1
@sunny_patel: It is so because you are passing the "vector<int>" by value and not by reference (and thus triggering the "copy" on every call). Try changing the argument to initializeA, initializeB to "vector<int> const &" instead.
(23 May '13, 22:18)

Wrote the code using RMQ. Can anybody guess where did I go wrong ?
answered 21 May '13, 19:24
I've an exactly similar code which got AC: http://www.codechef.com/viewsolution/2120000 The only difference is printing of decimal simply based on Modulo 2 for the diff instead of using "double" precision. Wonder if the precision of double caught up on you given that bi's could be of the order of 10^8?
(23 May '13, 21:53)
That is true. Double precision should give up to 15 digits precision atleast. Infact your solution gives AC to me.. :) http://www.codechef.com/viewsolution/2178141 [ used C++ 4.3.2 with include for cmath]
(24 May '13, 17:06)
1
Err.. Ain't it correct? In case2, '3' gets burned out from one side and then '12' burns out from the other (only) side again, taking 3+12 = 15? (similarly 14 for case3)
(24 May '13, 21:38)

nice to learn such wonderful ways.. thank you.. answered 14 May '13, 16:19

http://ww2.codechef.com/viewsolution/2106785. See this nice solution. It is AC without using any segment trees and some advanced technique :) answered 15 May '13, 20:44
Nice :) I think test cases can be prepared to fail this solution :) But I do appreciate the intelligence used in the solution.
(15 May '13, 22:32)
The approach is ingenious in a IOI style contest where partial marks are given.But I think it will get TLE in most judges.
(07 Feb '14, 03:15)

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 datastructures. answered 15 May '13, 11:52

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. answered 20 May '13, 04:20
2
Just change float to double in line 117 to get AC. :)
(25 May '13, 18:17)
Thanks a lot ! Finally got it accepted :)
(28 May '13, 07:29)

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 .. answered 19 May '13, 15:41
4
i too did this problem referring to topcoder tuts. i had the same question as you, and answer is pretty straight forward. ie If someone gave you bubble sort algorithm to sort in ascending order and then told you to modify it for descending order sorting,what changes will you make? That's right, that's the answer. just play with greater than/less than signs :) you can check my solution, i have done same approach as you are talking about and also have included topcoder algo in comments. AC code's link is there 2 questions above yours. PS there might be better approach bt mine answers ur doubt:)
(19 May '13, 16:08)
haha well explained :P
(19 May '13, 23:05)
Or you can just change the sign of the data items and use the same code (minimum) for both. My solution is based upon this trick.
(28 May '13, 21:42)

please some one help me in this code...http://www.codechef.com/viewsolution/2172202...giving wrong answer..cross checked many times... :( answered 20 May '13, 14:02

@mkagenius I again changed the code but getting WA :( please help me :( my solution id is :2183210 answered 28 May '13, 15:32

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 answered 31 May '13, 23:49
i answered in the other topic. your solution's worst case is when the input sequence of sticks is sorted.
(02 Jun '13, 01:41)

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. answered 07 Jun '13, 19:59
Got the reason for runtime error. But still I have doubt about how the solutions using two arrays of size 10000 are getting accepted.
(07 Jun '13, 20:14)
Finally accepted.! But still have the above doubt.
(08 Jun '13, 00:08)

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 answered 18 Jun '13, 22:54

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 answered 23 Jan '14, 15:07
1
I think it returns wrong answer for
last test is 6, not 7 as your code returns.
(23 Jan '14, 15:09)
Thanks a lot @betlista.. got my mistake and finally got AC…:)
(23 Jan '14, 19:25)

I get WA,can anyone tell me what am I doing wrong? My submission http://www.codechef.com/viewsolution/3339304 answered 07 Feb '14, 03:45

Hey Though I have test a lot of test cases and have considered the double part still the WA..:( heres my sol: http://www.codechef.com/viewsolution/3655905 .plz help..:( answered 30 Mar '14, 11:26

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... http://ideone.com/nJYO09 answered 11 Apr '14, 22:34

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 answered 26 Apr '14, 19:57

http://www.codechef.com/viewsolution/3902702 Can view my sol here. Not getting where is the prob,getting correct answer for all test cases answered 13 May '14, 19:53

unable to figure out whats wrong with this? http://www.codechef.com/viewsolution/3963394 answered 02 Jun '14, 03:47

What would the fault be in my solution? http://www.codechef.com/viewsolution/4069045 answered 12 Jun '14, 17:53

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 :) Here is my solution http://www.codechef.com/viewsolution/4170573 answered 01 Jul '14, 23:25

The below line, seems to give errors.
While,
gives, AC. I am perplexed, what is causing the error ? AC Solution and WA Solution. answered 03 Sep '14, 14:47

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 answered 26 Jun '15, 16:20

I think there is a mistake in the above formula..it should be m + max( (Mm)/2 , M' ) and not m + max( (Mm)/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? answered 14 May '13, 22:13

Segment trees need way too much memory to be allocated. Check out Sparse tables instead here answered 17 May '13, 21:39
Umm, a segment tree takes linear memory while a sparse table takes NlogN space. These are also the bounds for preprocessing time. Sparse table's advantage is that it answers queries in O(1) rather than O(logN).
(17 May '13, 23:18)

That was a really nice problem ;)
one of the best questions I have solved so far! kudos to the problem setter
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( (Mm)/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.
I think the time for all the matches to burn out completely should be m + max( (Mm)/2 , M')
@ravi1krishna3 : yes I also think that its wrong there M'/2.... wonder nobody noticed it....
@ravi1krishna3 Fixed.
http://ww2.codechef.com/viewsolution/2106785. See this nice solution. It is AC without using any segment trees and some advanced technique :)