You are not logged in. Please login at 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 '18, 20:45

ay2306's gravatar image

accept rate: 11%

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 '18, 00:20

m0nk3ydluffy's gravatar image

accept rate: 66%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 02 Jul '18, 20:45

question was seen: 139 times

last updated: 03 Jul '18, 00:20