Box Stacking Variation-Dynamic Programming

Question

Question 1: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.

Question 2: The above question was raised to 3 dimensions.

Question 3: The above question was then raised to k dimensions.

I believe we can apply dynamic programming to the above question.But

"A slab i can be put on slab j if both dimensions of i are less than that of j".

Not getting a clear idea on how to sort based on both the dimensions.

By maximum do you mean "maximum cardinality"- the number of slabs in the stack, or "maximum size"- the actual size of the resulting stack? — Ron Teller
– Ron Teller, Commented Mar 11, 2014 at 7:19
@shole: Nope.This was one of the question when my friend attended Amazon interview for SDE. — Rahul Kurup
– Rahul Kurup, Commented Mar 11, 2014 at 9:19

Ron Teller · Accepted Answer · 2014-03-11 11:18:54Z

4

I don't think Dynamic Programming is necessary in this problem, here's my suggestion:

Create a graph G with a vertex set V- representing all the slabs, and no edges. ( O(|V|) )
For each pair of slabs i and j in V, check if one can be on top the other (compare any number of dimensions). Say slab i can be on top of slab j, add an edge i->j to the graph. If i and j are of the same dimensions, a single edge should be added. ( O(|V|^2) )

The resulting graph is a DAG, since for any 3 slabs i,j,k , if i can be on top j, and j can be on top k, then k cannot be on top of i.

In order to avoid cycles when 3 or more slabs are of the same size (e.g. i->j, j->k, k->i), if 2 slabs are of the same size, the direction of the edge will be from the smaller index to the larger (e.g. if i and j are equal in dimensions, then the edge we'll add is i->j)
Find the longest path in G. This path represent the stack with the maximum number of slabs.

Finding such path in a DAG is an easy task and can be performed in linear time ( O(|V|+|E|) ).

The total running time of this algorithm is O(|V|) + O(|V|^2) + O(|V|+|E|) = O(|V|^2).

edited Mar 11, 2014 at 11:18

answered Mar 11, 2014 at 7:31

Ron Teller

1,8901 gold badge12 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

shole Over a year ago

just a minor question on step 2, if the size are same, why dont we add two edges? say there are 3 same sizes boxes A,B,C, won't we possibly get A->B and C->B which leads the longest path wrong?

Ron Teller Over a year ago

@shole We can't add both directions because we'll create a cycle. about the case you mentioned: there must also be an edge A->C or C->A, as they are all equal. no matter how you'll determine the direction of the edge, you'll always have a path containing all the equal slabs.

user3401643 · Accepted Answer · 2014-03-11 12:02:59Z

2

This is a Dynamic programming problem.

To solve this problem we need to figure out smaller sub-problem that solves larger set of problem. Let us say, Stack[i] indicate largest possible stack when input from 0 to i and this stack contains ith slab as its last slab. Then Stack[i] can be represented as:

if:AreaCover(Stack[j] > Stack[i])
    Stack[i] = Max{1 + Stack[j]} for all j [0 to i-1]

Here AreaCover is generic function which will return true (in all 3 questions) if a area condition is met.

Steps:

*Sort input as it is increasing on area.
*Build Stack[i] for all i [0 to n-1].
*Find Max value in Stack Array.

edited Mar 11, 2014 at 12:02

answered Mar 11, 2014 at 11:57

user3401643

1101 silver badge7 bronze badges

2 Comments

shole Over a year ago

can u elaborate more on "sort input as it is increasing on area"? for eg, (5,5) & (1,9) which would come first?

user3401643 Over a year ago

(5, 5) will comes first as its area 25 is greater than 9. Although (5, 5) would not be able to cover (1, 9) which is ok. The way this algo progresses is, at any time we have Max Slabs number at any moment that end with slab number i (This is required as we need to compare with this slab and if satisfies the criteria then we add that many slabs). When we are done with populating Stack array there would be a slab which will be sitting on top of max stack of slabs which we will discover by iteration.

Collectives™ on Stack Overflow

Box Stacking Variation-Dynamic Programming

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related