CareerCup

You have 3 variables to sort for each box - L, B and H. So sort by L, then by B and then by H. Sorting takes nlogn. This is 3 times nlogn i.e ~ nlogn. You run through the list one last time to get the answer. So the total time is
O(3nlogn) + O(n). This time is less than n^2. Am I missing something?

dynamic programming

#include<iostream>
using namespace std;

void find(int* l , int* b , int* h, int size)
{
int max[size];
int boxes[size];


for(int i = 0 ; i < size ; i++)
{
max[i] = 0;
boxes[i] = 0;
}

max[0] = 1;
boxes[0] = 0;

int maxcount = -1;

for(int i = 1 ; i < size ; i++)
{

bool smallerBox = false;
for(int j = 0 ; j < i ; j++)
{
if(l[j] < l[i] && b[j] < b[i] && h[j] < h[i] && max[j] + 1 > max[i])
{


smallerBox = true;

max[i] = max[j] + 1;
boxes[i] = j;
}
}

if(smallerBox == false)
{
max[i] = 1;
boxes[i] = i;
}

if(maxcount < max[i])
{
maxcount = max[i];
}
}


for(int i = 0 ; i < size ; i++)
{
if(max[i] == maxcount)
{
int box = i;
while(true)
{
cout << box << " ";

if(max[box] == 1)
{
break;
}

box = boxes[box];
}
}
cout << endl;
}
}

int main()
{
int l[4] = {2 , 1 , 3, 4};
int b[4] = {1 , 3, 2, 4};
int h[4] = {1 , 2, 2, 4};

find(l, b, h, 4);
}

I can't think of a way to do this in NlgN AHHH. I can do it in N^2 with a very low constant, grr!

I don't think it is possible to do it in NlgN now that I think about it, because if box X does not fit in box Y does not mean box Y does not fit in box X, so you can't really divide and conquer because you need to check every box against every other box, excluding those boxes that are subsumed by another.

I'm not following how this sort by LBH is going to work? Show me code because what do you mean sort by? You have to store the relation between the L B and H somewhere, otherwise when you resort you lose that data?

One thing is for sure that the largest subset we obtain will be a sorted order of boxes in descending order of their volumes, beginning with the outermost box.

So its best to first sort all the boxes in increasing/decreasing order of their volumes....

beginning with the largest volume box -
create a collection of boxes that fit into the largest box, say box A

if a box, say box B, doesn't fit in box A, start creating a collection of box B too...

for every subsequent box, test it against both the collections and add it to both the collections if it fits both.

continue this till the last box is reached.

the largest collection is the required solution..

i have not coded it... it just came as a different approach to my mind... comments welcome

you cannot do it based on the volume... consider the example below:
box A: l=10,b=20,c=30 -> volume=6000
box B: l=25,b=10,c=20 -> volume=5000
but still box B cannot fit in box A

i think a radix sort approach will help. First sort on length. Now we don't need to sort but just eliminate. Keeping this same order start from box with max. length, start comparing the breadth. If there are more boxes below it with breadth smaller then keep it else remove this box from consideration. Then goto the next box(with second largest length) and do the same.
After that do the same thing with the height. Any comments ?

http://en.wikipedia.org/wiki/Partially_ordered_set
The binary relation is Containment.

Any idea here Mr LOLer?
:p:p

this is a twist of longest increasing subsequence.

longest increasing subsequence problem:

for an array 9,4,6,3,10 : find a max set of elements where it is increasing. here it is 4,6,10.

to find the the longest increasing sequence, we maintain a lookup table, where the ith location indicates the maximum increasing value, for that input.

extending this idea to the current problem. given input is :

{7,8,9},{5,6,8},{5,8,7},{4,4,4}.

the lookup table for this problem should hold at each ith location, the maximum number of boxes that can be filled for the ith input.

to ease the computation we sort (descending) input array with one of the dimensions ( in this case the input is already sorted by length.

formula

Sj= max(Sk)+1 where 0<=k<j and l,b,h are larger to given input.

example:
A - {7,8,9}
B - {5,6,8}
C - {5,8,7}
D - {4,4,4}

0 A B C D
S 0 1 2 2 3

so 3 is the max. # of boxes that can be filled.

example 2 from Anonymous on Feb 11


int l[5] = { 2, 6, 1, 3, 4 };
int b[5] = { 1, 5, 3, 2, 4 };
int h[5] = { 1, 7, 2, 2, 4 };

A - { 2,1,1}
B - { 6,5,7}
C - { 1,3,2}
D - { 3,2,2}
E - { 4,4,4}

descending sort them by length we get

B - { 6,5,7}
E - { 4,4,4}
D - { 3,2,2}
A - { 2,1,1}
C - { 1,3,2}

0 B E D A C
S 0 1 2 3 4 5

so we have 5 boxes that can fit. we can also maintain additional information of its predecessor to know which last box best fit the given input.

cheers

fragzilla could you please elaborate your solution a little in depth with another suitable example as i see for the above example there are only 4 boxes that can fit into each other and that seems to be the maximum subset of boxes that can fit in each other. (but your computation yields 5). Either i am computing incorrectly or there is some problem with the approach.

what about orientation?
3,4,5 can fit into 6,5,4

how do we handle such cases? or this is not allowed?

TWISTED RADIX SORT (Decrement) WILL BE ENOUGH TO FIND THE SOLUTION OF THIS

(7,8,9)(5,6,8)(5,8,7)(4,4,4)

Sorting x Column will result as:

  x y z 
A 7 8 9  
B 5 6 8  
C 5 8 7  
D 4 4 4  

Now sort y column without disturbing the sorted order of previous column, it will result as:

  x y z
A 7 8 9 
C 5 8 7 
B 5 6 8 
D 4 4 4 

Now sort z, without disturbing previous columns sorted order.

  x y z
A 7 8 9  
C 5 8 7  
B 5 6 8  
D 4 4 4 

Now, we will compare rows A & C, as y column values are same, we will omit C and move to row B, again compare value, no column value is same & A>B. We will move to row D, again no column value is same & B>D.
So Solution is ABD.
Is this approach fine?????

similar to box stacking dynamic programming problem:

1. sort the boxes in decreasing order of their volumes. this defines the order of the sequence that the subsequence shall abide to while finding out the largest subsequence
2. instead of the constraint that the subsequence should be strictly increasing as in the case of longest increas(ing subsequence problem we have here constaint that the current box to be stacked inside the previous subsequence shall be stricly less in each of the three dimensions.
3. if i define,
H(j): the max no of boxes i can put inside each other s.t. jth box is the one that is the most inside(that is the last element of the subsequence as in the LCS problem)

H(j) = max(H(i) for all i<j s.t. h(i)>h(j);w(i)>w(j);d(i)>d(j)) + 1 ( for the jth box)

thus after builing the H[] we find max(H(j) for all j) which is the answer.

order (O(n^2))