Tower of Babylon Solution – SPOJ.com

Problem statement:

Given n different types of blocks. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon each other so that the resulting tower is as high as possible. Of course the blocks can be rotated as desired before stacking. However for reasons of stability a block can only be stacked upon another if both of its baselines are shorter.

Problem Link:

https://www.spoj.com/problems/BABTWR/

Example

Sample input:
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
Sample output:
342

Tower of Babylon Solution

Approach

This problem is similar to finding the longest increasing subsequence (LIS).

Let’s consider all the rotations of a block and add it to an array of structure of block [Block]. Block is a data structure with three integer variables x, y, and z.

Since we need the tallest tower, we sort all the blocks in an increasing order of their dimensions by x, y and then z.

Optimal Substructure

After that we traverse block array and find the optimum solution, where optimum solution is maximum of the following:

  1. Tallest tower obtained by n-1 elements, excluding nth element.
  2. nth element + tallest tower obtained by n-1 elements

Then, LIS(i) [Longest Increasing Sequence] can be recursively written as: 

// 'z' is the z or height dimension of the block
if LIS[i] < LIS[j] + block[i].z
  LIS(i) = block[i].z + LIS[j] where 0 < j < i;
else 
  LIS(i) = 1, if no such j exists.
ans = MAX(ans, LIS[i])

Code Implementation

//
//  main.cpp
//  Tower of Babylon
//
//  Created by Himanshu on 17/09/21.
//

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

struct block {
 int x,y,z;
};

bool cmp(const struct block &a,const struct block &b) {
    if(a.x != b.x)
        return (a.x < b.x);
    else if(a.y != b.y)
        return (a.y < b.y);
    else
        return (a.z < b.z);
}

block newBlock(int p,int q,int r) {
    block b;
    b.x = p;
    b.y = q;
    b.z = r;
    return b;
}

int main() {
    int n, ans, p, q, r;
    scanf("%d",&n);
    
    // Since each block can be rotated in 6 ways, 1 for each face
    int N = 6*n;
    block b[N];
    int lis[N];
    
    // Input terminates for n = 0, according to problem statement
    while(n != 0) {
        int j = 0;
        ans = 0;
        
        for(int i=0; i<n; i++) {
            scanf("%d %d %d",&p,&q,&r);
            
            // Adding all the combinations obtained by rotating a cuboid
            b[j++] = newBlock(p,q,r);
            b[j++] = newBlock(q,r,p);
            b[j++] = newBlock(r,p,q);
            b[j++] = newBlock(q,p,r);
            b[j++] = newBlock(r,q,p);
            b[j++] = newBlock(p,r,q);
            
        }
        sort(b,b+N,&cmp);
        
        for(int i=0;i<N;i++) {
            lis[i] = b[i].z;
            for(j=0;j<i;j++) {
                
                // To check if jth block can be placed above ith block
                if((b[j].x < b[i].x && b[j].y < b[i].y) || (b[j].x < b[i].y && b[j].y < b[i].x)) {
                    //Optimal solution by including b[i] or not
                    lis[i] = max(lis[i],(lis[j]+b[i].z));
                }
            }
            ans = max(ans,lis[i]);
        }
        
        printf("%d\n",ans);
        scanf("%d",&n);
 }
    
 return 0;
}

Here’s a working example:

https://ideone.com/PIY9HR

Leave a Reply

Your email address will not be published.