MSTICK - Editorial

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.

17 Likes

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?

1 Like

nice to learn such wonderful waysā€¦ thank youā€¦

2 Likes

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?

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

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

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

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

1 Like

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 ā€¦

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

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

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

4 Likes

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.

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

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

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.

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

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

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

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: