×

# Can you explain how editorial reached this conclusion?

 0 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 3★ay2306 192●9 accept rate: 13%

 2 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. answered 03 Jul, 00:20 51●3 accept rate: 66%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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