CODEWITHSUNDEEP
c++algorithmdynamic-programming
Felipe
Felipe

Reputation: 697

Construct biggest stacked tower with blocs and restriction

Problem

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

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

Input

The input contains several test cases. The first line of each test case contains an integer N (1 <= N <= 10^3), representing the number of cylinders arranged on the table, following N rows, each row having a height h (1 <= h <= 1000) of the cylinder in centimeters, the radius r (1 <= r <= 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, but it takes more than 8 secs to give a answer with a big input (inside the limits); Is this solution right for this problem ? Is there another algorithm ?

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

#define MAX 1000

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

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){}
};

inline bool compare (const cylinder_t &i,const cylinder_t &j) {
    return i.r > j.r;
}

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 - cylinder[last_cylinder_onStack].c + 4)%4 == 1)
        return false;

    return true;
}

int memo[MAX][MAX];
int dp(int tower_size, int size, int last_cylinder_onStack){
    if(tower_size == size)
        return 0;

    if(last_cylinder_onStack != NON && memo[tower_size][last_cylinder_onStack] != -1)
        return memo[tower_size][last_cylinder_onStack];

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

    if(last_cylinder_onStack == NON)
        return maxHeight;
    return memo[tower_size][last_cylinder_onStack] = maxHeight;
}

int main(void){
    //clock_t t;
    //t = clock();

    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)];
        }

        std::sort(cylinder, cylinder + n, compare);

        memset(memo, -1, sizeof(memo));
        printf("%d centimeter(s)\n",dp(0,n, NON));
    }

    //t = clock() - t;
    //printf("Took %lf seconds to execute \n",((double)t)/CLOCKS_PER_SEC);
}

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");
    }

}

Upvotes: 1

Views: 407

Answers (1)

Petr
Petr

Reputation: 9997

It is quite strange that your dp table has both tower_size and last_cylinder_on_stack parameters. I think that dp should depend only on last_cylinder_on_stack. In the recursion function, you know the last cylinder on stack, so you clearly should loop only from last_cylinder_on_stack+1

So I think that you should get rid of last_cylinder_onStack parameter and have the main loop as

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

Upvotes: 3

Related Questions