Revisions to Construct biggest stacked tower with restriction

Rollback to Revision 3

Source Link

edited Sep 14, 2015 at 21:00

13.3k
3
38
93

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

#define MAX 1000

#define NON -1
#define RED 31
#define ORA 2
#define BLUGRE 13
#define GREBLU 04

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 compare canPut(const cylinder_tint &ii,const cylinder_tint &jlast_cylinder_onStack) {
    if (last_cylinder_onStack == NON)
        return itrue;
    
    if(cylinder[i].r >>= jcylinder[last_cylinder_onStack].r;
}r)
        return false;
cylinder_t cylinder[MAX];   
inline bool canPut  if(intcylinder[i].c i,== intRED last_cylinder_onStack&& cylinder[last_cylinder_onStack].c == ORA){
        return false;
    
    if(last_cylinder_onStackcylinder[i].c == NONORA && cylinder[last_cylinder_onStack].c == BLU)
        return true;false;
    
    if (cylinder[i].rc >=== BLU && cylinder[last_cylinder_onStack].rc == GRE)
        return false;
    
    if((cylinder[i].c -== GRE && cylinder[last_cylinder_onStack].c + 4)%4 == 1RED)
        return false;
        
    return true;
}

int

std::unordered_map<int, memo[MAX][MAX];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(last_cylinder_onStack 
 != NON && if(memo[i][last_cylinder_onStack] != -1)
        return memo[i][last_cylinder_onStack];
    
    int maxHeight = 0;
    for (int c = i;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;
    if(last_cylinder_onStack == NON)
     }
   return maxHeight;}
    return memo[i][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::sortmemset(cylinderonStack, cylinder + nfalse, comparesizeof(onStack));
        
        memset(memo, -1, sizeof(memo));
        printf("%d centimeter(s)\n",dp(0,n, NON));
    }
    
    //t = clock() - t;
    //printfmemo.clear("Took %lf);
 seconds to execute \n",((double)t)/CLOCKS_PER_SEC);}
}

This solution is taking much more than 1 sec with a big inputinputs. How can i make it faster ? some people just made it in almost 0 secs.

#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 i, int size, int last_cylinder_onStack){
    if(i == size)
        return 0;
 
    if(last_cylinder_onStack != NON && memo[i][last_cylinder_onStack] != -1)
        return memo[i][last_cylinder_onStack];
    
    int maxHeight = 0;
    for (int c = i; c < size; ++c) {
        if(canPut(c, last_cylinder_onStack)) {
            maxHeight = std::max(maxHeight, cylinder[c].h + dp(i + 1, size, c));
        }
    }
    
    if(last_cylinder_onStack == NON)
        return maxHeight;
    return memo[i][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);
}

This solution is taking much more than 1 sec with a big input. How can i make it faster ? some people just made it in almost 0 secs.

#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 ?

updated code and problem

Source Link

edited Sep 14, 2015 at 20:57

Felipe

597
1
5
13

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

#define MAX 1000

#define NON -1
#define RED 13
#define ORA 2
#define GREBLU 31
#define BLUGRE 40

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 canPutcompare (intconst icylinder_t &i,const intcylinder_t last_cylinder_onStack&j){
    if (last_cylinder_onStack == NON){
        return true;
    
    if(cylinder[i]i.r >=> cylinder[last_cylinder_onStack]j.r)r;
        return false;}
    
 cylinder_t cylinder[MAX];
inline bool ifcanPut(cylinder[i].c == RED &&int cylinder[last_cylinder_onStack].ci, ==int ORAlast_cylinder_onStack)
        return false;{
    
    if(cylinder[i].c == ORA && cylinder[last_cylinder_onStack].clast_cylinder_onStack == BLUNON)
        return false;true;
    
    if (cylinder[i].c == BLUr &&>= cylinder[last_cylinder_onStack].c == GREr)
        return false;
    
    if((cylinder[i].c == GRE &&- cylinder[last_cylinder_onStack].c + 4)%4 == RED1)
        return false;
        
    return true;
}

 

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

    
 if(last_cylinder_onStack != NON && if(memo[i][last_cylinder_onStack] != -1)
        return memo[i][last_cylinder_onStack];
    
    int maxHeight = 0;
    for (int c = 0;i; 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;
   
    if(last_cylinder_onStack == }NON)
    }    return maxHeight;
    return memo[i][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)];
        }
        
        memsetstd::sort(onStackcylinder, falsecylinder + n, sizeof(onStack)compare);
        
        memset(memo, -1, sizeof(memo));
        printf("%d centimeter(s)\n",dp(0,n, NON));
    }
    
      //t = memo.clearclock(); - t;
    }//printf("Took %lf seconds to execute \n",((double)t)/CLOCKS_PER_SEC);
}

This solution is taking much more than 1 sec with a big inputsinput. How can i make it faster ? some people just made it in almost 0 secs.

#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 ?

#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 i, int size, int last_cylinder_onStack){
    if(i == size)
        return 0; 

    if(last_cylinder_onStack != NON && memo[i][last_cylinder_onStack] != -1)
        return memo[i][last_cylinder_onStack];
    
    int maxHeight = 0;
    for (int c = i; c < size; ++c) {
        if(canPut(c, last_cylinder_onStack)) {
            maxHeight = std::max(maxHeight, cylinder[c].h + dp(i + 1, size, c));
        }
    }
     
    if(last_cylinder_onStack == NON)
        return maxHeight;
    return memo[i][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);
}

This solution is taking much more than 1 sec with a big input. How can i make it faster ? some people just made it in almost 0 secs.

added 133 characters in body

Source Link

edited Sep 14, 2015 at 19:01

Ethan Bierlein

15.8k
4
59
146

Will be arranged on the table, an amount of N\$N\$ cylinders.
Each cylinder has one color: Red, orange, green or blue.
Each cylinder has one heigth h\$h\$ and a base with radius of size r\$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.

The input contains several test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 10³)\$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 ≤ h ≤ 1000)\$h\$ \$(1 \le h \le 1000)\$ of the cylinder in centimeters, the radius r (1 ≤ r ≤ 1000)\$r\$ \$(1 \le r \le 1000)\$ of the cylinder base and a word p\$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\$N = 0\$, which should not be processed.

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
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

15 centimeter(s)
11 centimeter(s)
15 centimeter(s)    
11 centimeter(s)

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.

The input contains several test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 10³), 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.

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

15 centimeter(s)
11 centimeter(s)

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.

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.

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

15 centimeter(s)    
11 centimeter(s)

Don't need dynamic programming on title

Link

edited Sep 14, 2015 at 18:22

Felipe

597
1
5
13

Loading

Source Link

asked Sep 14, 2015 at 18:09

Felipe

597
1
5
13

Loading

Stack Exchange Network

Return to Question