×

SIMPLE

PREREQUISITES

Range Minimum Query, Simple Math

PROBLEM

You 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 EXPLANATION

For each query, the operation performed plays out in the following way

• All the matchsticks in the range L to R are lit from their front ends.
• The matchstick that burns quickest in the range L to R burns out and ignites all the other matchsticks on their rear ends.
• The matchticks in the range L to R now burn out twice as fast.
• All the other matchsticks burn out at their original rate.

We can find the time taken in all the steps above using only the following pieces of information for the segment L to R

• Quickest rate of burning for a match in the range L to R.
• Slowest rate of burning for all matches in the range L to R.
• Slowest rate of burning for all matches outside the range L to R.

EXPLANATION

For a given range L to R

• Let m denote the minimum time taken by some matchstick in the range L to R to burn out
• Let M denote the largest time taken by some matchstick in the range L to R to burn out
• Let M' denote the largest time taken by some matchstick outside the range L to R to burn out

The time taken by each of the steps in the scenario described above is as follows

• The matchstick that burns quickest, burns out
• Takes time m
• The following things happen in parallel
• The matchsticks in the range L to R now burn out twice as fast
• Takes time (M - m) / 2
• The matchsticks outside the range
• Takes time M'

Thus, the time taken for all the matches to burn out completely is

m + max( (M-m)/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 L-1 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 SOLUTION

Can be found here.

TESTER'S SOLUTION

Approach - 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".

2.4k128183169
accept rate: 14%

19.8k350498541

1

That was a really nice problem ;-)

(14 May '13, 15:36)
2

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

(14 May '13, 15:46)

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

(14 May '13, 16:09)
2

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

(14 May '13, 18:40)

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

(14 May '13, 18:47)
(14 May '13, 18:53)

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

(15 May '13, 10:44)
showing 5 of 7 show all

 4 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! :) answered 15 May '13, 13:04 1.3k●3●10●25 accept rate: 19% 1 Strange that. Not sure why that happened. May be your code was just under time limit and using vector took little extra to make it TLE. You can use single tree, but with addition data that is the tree will have two data in each node - max, min both. You will need to define a struct to accomplish this. Although it creates one tree but the complexity of code is not much simplified, I think. 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 but if someone can still help me with my first doubt! :) (16 May '13, 18:40) 1 @sunny_patel: It is so because you are passing the "vector" by value and not by reference (and thus triggering the "copy" on every call). Try changing the argument to initializeA, initializeB to "vector const &" instead. (23 May '13, 22:18) srihari4★
 4 Wrote the code using RMQ. Can anybody guess where did I go wrong ? Link to my code : http://ideone.com/lLzB7a answered 21 May '13, 19:24 5.7k●26●68●68 accept rate: 17% 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) srihari4★ 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) srihari4★ 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) srihari4★
 2 nice to learn such wonderful ways.. thank you.. answered 14 May '13, 16:19 561●7●16●26 accept rate: 8% Thanks, my pleasure :) (15 May '13, 22:22)
 2 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 21●1●3●9 accept rate: 0% 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)
 1 minimum in a range can be found in O(N) by simply traversing the array of integers. O(N) is better than O(NlogN) , so please kindly tell me, where am i missing the point? answered 14 May '13, 15:50 561●7●16●26 accept rate: 8% 2 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). (14 May '13, 15:56) n2n_5★ You precompute minima and maxima for various ranges in O(N*logN) and then answer all the queries in O(1). (14 May '13, 17:01) milhaus2★ 1 @milhaus but there are N^2 ranges possible, which will make it O(N^2*logN). (14 May '13, 21:47) banarun4★ In this question you have to answer Q queries. So, surely you have to find all four minimum & maximums for different ranges every time for every query. So, now if you have answer a single query you have to run your program of O(N) complexity all four times. Then if you have to answer Q query then complexity will be O(NQ). But using this algorithm you can answer a query in O(log N) time which is smaller than O(N). All what is required is that you have to preprocess the array into a segment tree which takes O(N) time. This gives a approach which is way faster than O(NQ). (16 May '13, 19:30)
 1 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. answered 15 May '13, 11:52 2★sg1993 46●1●2●4 accept rate: 0% 1 Thanks. I did not expect so many people will like it. :) (15 May '13, 22:22)
 1 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 16 accept rate: 0% 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)
 0 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 0●1 accept rate: 0% 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) yo_baby1★ 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) Debanjan2★
 0 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 47●1●2●5 accept rate: 0% Showing invalid Solution ID.. (02 Jun '13, 10:05)
 0 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. answered 23 May '13, 16:17 1★hrculiz 50●6●9●14 accept rate: 0%
 0 @mkagenius I again changed the code but getting WA :( please help me :( my solution id is :-2183210 answered 28 May '13, 15:32 1★hrculiz 50●6●9●14 accept rate: 0%
 0 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 2★noahwhoo 1●1●1●2 accept rate: 0% 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)
 0 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 3★tutulive 0●1 accept rate: 0% 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) tutulive3★ Finally accepted.! But still have the above doubt. (08 Jun '13, 00:08) tutulive3★
 0 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 1●1 accept rate: 0%
 0 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 http://ideone.com/sbcpML answered 23 Jan '14, 15:07 1●2●3 accept rate: 0% 16.9k●49●115●225 1 I think it returns wrong answer for 6 3 4 5 1 2 3 3 0 0 1 2 0 2 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)
 0 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 1 accept rate: 0%
 0 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 2★wonder 361●18●37●69 accept rate: 0%
 0 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 1 accept rate: 0% It seems you found the error, right? (11 Apr '14, 22:55)
 0 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 86●2●4●6 accept rate: 0%
 0 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 3★noops 41●1●1●4 accept rate: 20%
 0 unable to figure out whats wrong with this? http://www.codechef.com/viewsolution/3963394 answered 02 Jun '14, 03:47 41●2●6 accept rate: 8%
 0 What would the fault be in my solution? http://www.codechef.com/viewsolution/4069045 answered 12 Jun '14, 17:53 21●1●3●7 accept rate: 0%
 0 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 2★ghaieth 56●2●3●11 accept rate: 0%
 0 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. answered 03 Sep '14, 14:47 3★mjnovice 135●3●5●13 accept rate: 0%
 0 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 1 accept rate: 0%
 -1 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? answered 14 May '13, 22:13 0 accept rate: 0% The above formula is correct. Analyze. (07 Jun '13, 20:05) tutulive3★
 -1 Segment trees need way too much memory to be allocated. Check out Sparse tables instead here answered 17 May '13, 21:39 3★evandrix 165●1●4●8 accept rate: 0% 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) msasha4★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,768
×1,191
×281
×18

question asked: 14 May '13, 15:19

question was seen: 11,048 times

last updated: 27 Jun '15, 11:05