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

×

Can you explain how editorial reached this conclusion?

In this question, the editorial solves the question with formula max(L+h1,a[w2]). I don't get it how did he reach the conclusion. And also the problem set has a tag of the data structure. Which data structure should be used here?

asked 02 Jul, 20:45

ay2306's gravatar image

3★ay2306
1929
accept rate: 13%


I'll try to explain how to reach the formula.

Lets solve a very easy version of the problem first i.e. suppose a box gets destroyed before the next box arrives. So whenever a box arrives, there are no other boxes on the staircase. Now, suppose you have to answer the same query for a box with width $w_{i}$. The answer for this query would simply be $a[w_{i}]\ $. Why? Since our box has width $w_{i}\ $, it spans from the complete left to the $w_{i}$'th stair, thus the answer should be the largest height between indices $1$ and $w_{i}$ (considering 1 based indexing). Also, we know that $a$ represents a staircase, increasing from left to right i.e. array $a$ is in non-decreasing order, so the stair having maximum height between indices $1$ and $w_{i}$ should be the $w_{i}$'th stair. Thus the answer in this case is simply $a[w_{i}]$.

Keeping in mind the easier case, lets come back to the original problem. Now older boxes are not destroyed. Suppose the first box to fall has height $h_{1}$ and width $w_{1}$ and the second box to fall has height $h_{2}$ and width $w_{2}$. The answer for the first box will be $a[w_{1}]$ since this is similar to the easier case we discussed earlier as this is the first box. Let this answer (for the first box) be $L$ ( = $a[w_{1}]$). Now, the answer for the second box may be affected by the first box. If the first box was destroyed, the answer for the second box would be $a[w_{2}]$. But what happens if the top of the first box reaches a height greater that the height of the $w_2$'th stair. If this happens then the second box will collide with the first box before the $w_2$'th stair and remain there. So the answer for the second box = $max(height\ of\ the\ top\ of\ the\ previous\ box,\ a[w_{2}]) = max(L+h_{1},\ a[w_{2}])$.

This problem could be solved without any special data structure because all the boxes always begin at the first staircase i.e. on the extreme left. You would need something like a segment tree to solve the case where the starting position of the boxes is also specified.

I hope I was clear enough.

Do have a look at the picture given in the problem statement for a better understanding of the cases we discussed.

link

answered 03 Jul, 00:20

m0nk3ydluffy's gravatar image

6★m0nk3ydluffy
513
accept rate: 66%

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:

×1,372
×294
×30
×17

question asked: 02 Jul, 20:45

question was seen: 129 times

last updated: 03 Jul, 00:20