MSTICK - Editorial

editorial
may13
segment-tree
simple
simple-math

#1

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.


#2

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?


#3

nice to learn such wonderful ways… thank you…


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


#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:


#7

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


#8

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


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


#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 ?


#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 ? http://www.codechef.com/viewsolution/2188068


#16

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.


#17

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


#18

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


#19

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


#20

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: