You are not logged in. Please login at www.codechef.com to post your questions!

×

MSTICK - Editorial

13
5

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.

This question is marked "community wiki".

asked 14 May '13, 15:19

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 22 May '13, 00:35

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

That was a really nice problem ;-)

(14 May '13, 15:36) betlista ♦♦3★
2

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

(14 May '13, 15:46) rishul_nsit4★

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.

(14 May '13, 16:09) aashish_iitm2★
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) ravi1krishna33★

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

(14 May '13, 18:47) devanshug4★
(14 May '13, 18:53) gamabunta1★

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) timepass1232★
showing 5 of 7 show all

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! :)

link

answered 15 May '13, 13:04

sunny_patel's gravatar image

2★sunny_patel
1.3k31025
accept rate: 19%

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

  2. 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) mkagenius4★
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) sunny_patel2★
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) srihari4★

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

link

answered 21 May '13, 19:24

bit_cracker007's gravatar image

3★bit_cracker007
5.7k266868
accept rate: 17%

edited 24 May '13, 10:40

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★

nice to learn such wonderful ways.. thank you..

link

answered 14 May '13, 16:19

sumanth232's gravatar image

4★sumanth232
56171626
accept rate: 8%

Thanks, my pleasure :)

(15 May '13, 22:22) mkagenius4★

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

link

answered 15 May '13, 20:44

timepass123's gravatar image

2★timepass123
21139
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) mkagenius4★

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) imran221b4★

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?

link

answered 14 May '13, 15:50

sumanth232's gravatar image

4★sumanth232
56171626
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 <o(n), o(logn)=""> approach which is way faster than O(NQ).

(16 May '13, 19:30) devanshug4★

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.

link

answered 15 May '13, 11:52

sg1993's gravatar image

2★sg1993
46124
accept rate: 0%

1

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

(15 May '13, 22:22) mkagenius4★

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.

link

answered 20 May '13, 04:20

beriaanirudh's gravatar image

4★beriaanirudh
16
accept rate: 0%

2

Just change float to double in line 117 to get AC. :)

(25 May '13, 18:17) mkagenius4★

Thanks a lot ! Finally got it accepted :)

(28 May '13, 07:29) beriaanirudh4★

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

link

answered 19 May '13, 15:41

frompondy's gravatar image

2★frompondy
01
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) sunny_patel2★

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★

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

link

answered 20 May '13, 14:02

shivendra1401's gravatar image

2★shivendra1401
47125
accept rate: 0%

Showing invalid Solution ID..

(02 Jun '13, 10:05) mayankj081★

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.

link

answered 23 May '13, 16:17

hrculiz's gravatar image

1★hrculiz
506914
accept rate: 0%

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

link

answered 28 May '13, 15:32

hrculiz's gravatar image

1★hrculiz
506914
accept rate: 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

link

answered 31 May '13, 23:49

noahwhoo's gravatar image

2★noahwhoo
1112
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) cyberax ♦3★

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.

link

answered 07 Jun '13, 19:59

tutulive's gravatar image

3★tutulive
01
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★

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

link

answered 18 Jun '13, 22:54

swap_coder's gravatar image

1★swap_coder
11
accept rate: 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

link

answered 23 Jan '14, 15:07

gauravgulzar's gravatar image

3★gauravgulzar
123
accept rate: 0%

edited 23 Jan '14, 15:08

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

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) betlista ♦♦3★

Thanks a lot @betlista.. got my mistake and finally got AC…:)

(23 Jan '14, 19:25) gauravgulzar3★

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

link

answered 07 Feb '14, 03:45

imran221b's gravatar image

4★imran221b
1
accept rate: 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..:(

link

answered 30 Mar '14, 11:26

wonder's gravatar image

2★wonder
361183769
accept rate: 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

link

answered 11 Apr '14, 22:34

archit1993's gravatar image

3★archit1993
1
accept rate: 0%

It seems you found the error, right?

(11 Apr '14, 22:55) betlista ♦♦3★

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

link

answered 26 Apr '14, 19:57

dwatson_bynes's gravatar image

2★dwatson_bynes
86246
accept rate: 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

link

answered 13 May '14, 19:53

noops's gravatar image

3★noops
41114
accept rate: 20%

unable to figure out whats wrong with this? http://www.codechef.com/viewsolution/3963394

link

answered 02 Jun '14, 03:47

ab13123002's gravatar image

5★ab13123002
4126
accept rate: 8%

What would the fault be in my solution? http://www.codechef.com/viewsolution/4069045

link

answered 12 Jun '14, 17:53

abhyudaya's gravatar image

2★abhyudaya
21137
accept rate: 0%

edited 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

link

answered 01 Jul '14, 23:25

ghaieth's gravatar image

2★ghaieth
562311
accept rate: 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.

link

answered 03 Sep '14, 14:47

mjnovice's gravatar image

3★mjnovice
1353513
accept rate: 0%

edited 04 Sep '14, 08:10

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

link

answered 26 Jun '15, 16:20

sagar0430's gravatar image

2★sagar0430
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?

link

answered 14 May '13, 22:13

md_ahmar91's gravatar image

2★md_ahmar91
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

link

answered 17 May '13, 21:39

evandrix's gravatar image

3★evandrix
165148
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
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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