Construct biggest stacked tower with restriction

Question

Problem

The problem is to build the tallest tower made up of cylinders, respecting all the rules.

• Will be arranged on the table, an amount of \$N\$ cylinders.
• Each cylinder has one color: Red, orange, green or blue.
• Each cylinder has one heigth \$h\$ and a base with radius of size \$r\$.
• To the build the tower, the cylinders should to be stacked, and the top cylinder should ever have the base smaller that the base of the cylinder below it. Except the first cylinder, it can have the base of any size, since there is no other cylinder below it.

There are also some restrictions very interesting on colors of the cylinders. They are described below.

• A red cylinder cannot to be put on an orange cylinder
• An orange cylinder cannot to be put on a blue cylinder
• A blue cylinder cannot to be put on a green cylinder
• A green cylinder cannot to be put on a red cylinder

Input

The input contains several test cases. The first line of each test case contains an integer \$N\$ \$(1 \le N \le 10^3)\$, representing the number of cylinders arranged on the table, following N rows, each row having a height \$h\$ \$(1 \le h \le 1000)\$ of the cylinder in centimeters, the radius \$r\$ \$(1 \le r \le 1000)\$ of the cylinder base and a word \$p\$, representing the color of the cylinder. The word can be: RED, ORANGE, GREEN, or BLUE. The end of input is indicated as \$N = 0\$, which should not be processed.

Output

For each test case, your program should print a single line with the value the height of the largest cylinders tower that can be built, followed by the word "centimeter(s)”.

Sample Input

5   
5 3 RED    
4 2 ORANGE   
1 1 GREEN    
3 5 ORANGE    
2 4 BLUE    
3    
10 10 ORANGE    
5 10 GREEN    
6 5 RED    
0

Sample Output

15 centimeter(s)    
11 centimeter(s)

I've tried to solve this problem with dynamic programming.

#include <cstdio>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <string.h>

#define MAX 1000

#define NON -1
#define RED 1
#define ORA 2
#define GRE 3
#define BLU 4

struct cylinder_t{
    int h,r,c;
    cylinder_t():h(0),r(0),c(0){}
    cylinder_t(int height, int radius, int color):h(height),r(radius),c(color){}
};


cylinder_t cylinder[MAX];
inline bool canPut(int i, int last_cylinder_onStack){
    if (last_cylinder_onStack == NON)
        return true;

    if(cylinder[i].r >= cylinder[last_cylinder_onStack].r)
        return false;

    if(cylinder[i].c == RED && cylinder[last_cylinder_onStack].c == ORA)
        return false;

    if(cylinder[i].c == ORA && cylinder[last_cylinder_onStack].c == BLU)
        return false;

    if(cylinder[i].c == BLU && cylinder[last_cylinder_onStack].c == GRE)
        return false;

    if(cylinder[i].c == GRE && cylinder[last_cylinder_onStack].c == RED)
        return false;

    return true;
}



std::unordered_map<int, std::unordered_map<int, int> > memo;
bool onStack[MAX];
int dp(int i, int size, int last_cylinder_onStack){
    if(i == size)
        return 0;

    if(memo[i][last_cylinder_onStack])
        return memo[i][last_cylinder_onStack];

    int maxHeight = 0;
    for (int c = 0; c < size; ++c) {
        if(!onStack[c] && canPut(c, last_cylinder_onStack)){
            onStack[c] = true;
            maxHeight = std::max(maxHeight, cylinder[c].h + dp(i + 1, size, c));
            onStack[c] = false;
        }
    }
    return memo[i][last_cylinder_onStack] = maxHeight;
}



int main(void){

    std::unordered_map<std::string, int> map;
    map["RED"]     = RED;
    map["ORANGE"]  = ORA;
    map["GREEN"]   = GRE;
    map["BLUE"]    = BLU;


    int n;
    while(scanf("%d",&n), n != 0){

        for (int i = 0; i < n; ++i) {
            int height,radius;
            char color[15];
            scanf("%d %d %s",&height,&radius,&color[0]);
            cylinder[i].h = height;
            cylinder[i].r = radius;
            cylinder[i].c = map[std::string(color)];
        }

        memset(onStack, false, sizeof(onStack));

        printf("%d centimeter(s)\n",dp(0,n, NON));

        memo.clear();
    }
}

This solution is taking more than 1 sec with big inputs. How can i make it faster ?

I've made a INPUT generator in JAVA for this problem:

import java.io.IOException;
import java.util.Random;


public class Main {

    public static void main(String[] args) throws IOException {
        Random r = new Random();
        String color[] = {"RED","ORANGE","GREEN","BLUE"};

        int t = 20;//number of test cases
        for (int i = 0; i < t; i++) {
            int n = r.nextInt(1000) + 1; //number of cylinders
            System.out.println(n);
            for (int j = 0; j < n; j++) {
                System.out.printf("%d %d %s\n",r.nextInt(1000) + 1,r.nextInt(1000) + 1,color[r.nextInt(4)]);
            }
        }

        System.out.println("0");
    }

}   

Answer 1

• An immediate candidate for optimisation is canPut. The color restrictions reveal some symmetry. If you map colors to numbers 0..3, you may notice that the each restrictions actually mean the same thing:

  (cylinder[i].c - cylinder[last_cylinder_onStack].c) % 4 == 1
  

  is prohibited. This is the only condition to be tested.

• I would also sort the cylinders by radius. This way you don't need to manually track the cylinders, and the dp loop reduces to

  for (int c = i + 1; c < size; ++c) {
      if(canPut(c, last_cylinder_onStack)) {
          maxHeight = std::max(maxHeight, cylinder[c].h + dp(i + 1, size, c));
      }
  }
  

• A map is a very heavyweight object. It has much memory overhead, doesn't have a good referential locality, and has a logarithmic time complexity. A map of maps is even more heavy. Since all your keys are integers, a simple 2D array, or vector of vectors if you wish (with constant insert and access time) would serve you much better.