nesting boxes

[nukeu666]

the question is we are given a number of boxes(length and width given)
box1 can be nested in box2 if l2>l1 and w2>w1
we keep nesting boxes till no other box fits in any other and this is the number we want

any tips on how to do this?

ex...we have 4 boxes (10,10),(5,5),(1,1),(1,11)...the answer we get is 2 coz in the we have only a (10,10) and (1,11) box remaining that wont fit in each other

[little joey]

Look at it as a graph problem: all boxes are vertices in the graph, and there is a directed edge from box1 to box2 iff box1 fits into box2. Then the problem translates to finding the longest path in the graph, or the 'all pairs longest path' which can be solved with a (slightly modified) Floyd-Warshall approach. If you want to be able to reconstruct the longest path, i.e. report the actual arrangement of boxes, you can keep and update a parent attribute.

[sohel]

This problem looks very similar to the 500 point problem in GCJI 2006 qualification.

My idea was a modified version of LIS.
Sort the points in terms of ascending values of x and for equal x sort in ascending order of y.

Then simply run a n^2 LIS, and keeping track of the parent(if the path is required).

For that problem, the number of boxes were 10000, so FW is likely to get TLE.

-- sohel

[nukeu666]

ill take a look at warshall

whats LIS??

[kodder]

i think this is LIS problem
use DP to slove it!!!

[misof]

LIS = longest increasing subsequence