## Tower of boxes

Moderator: Board moderators

### Tower of boxes

hi there,

i got this task last week but can't find a good algorithm to solve the problem. So here is the description:

You can build a stable tower with building bricks by not putting bigger bricks to smaller ones and if you don't put harder bricks into lighter ones. Make a programme which gives you the highest possible tower with n number of bricks.
Input:
In the first row of in.txt there is the number of cubes n (1 =<n =<1000). the following n line consisting two positive integer, a cube's sidelength and weight (both of them are not higher than 2000) there are no similar cubes which sidelength and wieght is the same
Output:
you have to write the highest possible stable tower's m number into out.txt. into the second row you have to write in the ordinal number m of the tower from bottom to top. by the height of the tower we mean the amount of all of the cubes's sidelength (not the number of cubes). if there are more than one solution, you can give whatever you want

example for input and output:
Input: Output:
5 3
10 3 2 1 5
20 5
15 6
15 1
10 2

there are limits on the program. Time limit: 0.2 sec. Memory limit: 16 Mb

I hope you can help me to solve this, i need to finish this till sunday. thx for all help
poko
New poster

Posts: 3
Joined: Mon Nov 22, 2010 9:32 pm

### Re: Tower of boxes

Oh soz, the input and output is a little bit mixed up
So here is the input:
5
10 3
20 5
15 6
15 1
10 2

and the output:
3
2 1 5
poko
New poster

Posts: 3
Joined: Mon Nov 22, 2010 9:32 pm

### Re: Tower of boxes

You can treat each brick as 3 different bricks. A brick can be represented as (length x breadth x height). For example a brick of dimension 1x2x3 can be thought of 3 bricks as 1x2x3 or 2x3x1 or 3x1x2. Apply Longest increasing Sub sequence problem such that max height of tower can be obtained

Code: Select all
`BS(index)         if(index = 1) return h[1]         if BS[index] return BS[index]   //memoization         for each prevIndex from index-1 to 1            if(l[index] <  length[prevIndex] && breadth[index] < breadth[prevIndex] && weight[index] < weight[previndex])                max = BS(prevIndex) + height[index]            if(BS[index] > max)               BS[index] = max               parent[index] = prevIndex`

parent[] will hold the stacking info to create brick stack with max height
prateekcaire
New poster

Posts: 1
Joined: Tue Nov 23, 2010 12:31 pm
Location: India

### Re: Tower of boxes

Sorry maybe i told you it was a brick but it's a cube. So length=breadth=height.
poko
New poster

Posts: 3
Joined: Mon Nov 22, 2010 9:32 pm