StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let's first try to solve this problem in 2-D:</p> <p>say you have rectangles with X's and Y's, and the question is similar (highest tower, but this time you only have to worry about one base dimension).<br> so first, you go over the whole collection, duplicating each rectangle by rotating it 90 degrees (swapping X and Y), except for squares (where X(1)=X(2) && Y(1)=Y(2)). this represents all possible variations.<br> then you sort them by their X side, from largest to smallest. in case of duplicate X value, you remove the one with the lower Y value.</p> <p>same principle applied in the 3-D scenario, only now you DONT just multiply the collection's size by 6 (every possible variants of the W, H, D) but rather by 2. you do this by dismissing all variations where the width is lower than the depth ( so for each i, W(i)>=D(i)), and then dismissing the variation where the height is not the highest nor the lowest of the three dimensions (because the other two variations can go one on top of the other and this one can't join in). again, you also dismiss duplications (where W(1)=W(2) && H(1)=H(2) && D(1)=D(2)).<br> Then you should sort by width, only this time you don;t throw away variations with the same width (because one may fit in a tower that another may not) then you can use the LIS algorithm as described above by @IVlad :</p> <pre><code>D[1] = h(1); D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists. </code></pre> <p>the trick was, you know that the width is the longest of the two, so you know the first element will not fit on top of any later element.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload