MSTICK - Editorial

[gamabunta]

PROBLEM LINKS

Practice
Contest

DIFFICULTY

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.

[betlista]

That was a really nice problem

[rishul_nsit]

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

[sumanth232]

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?

[n2n]

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).

[aashish_iitm]

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 http://en.wikipedia.org/wiki/Cartesian_tree.

[sumanth232]

nice to learn such wonderful ways… thank you…

[milhaus]

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

[ravi1krishna3]

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

[devanshug]

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

[gamabunta]

@ravi1krishna3 Fixed.

[banarun]

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

[md_ahmar91]

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?

[timepass123]

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

[sg1993]

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.

[sunny_patel]

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!

[timepass123]

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

[mkagenius]

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

[mkagenius]

Thanks, my pleasure

[mkagenius]

Nice
I think test cases can be prepared to fail this solution
But I do appreciate the intelligence used in the solution.