UVA – 437 – The Tower of Babylon – (DP, DAG)

  • Problem Statement : UVA – 437 – The Tower of Babylon
  • Type : Dynamic, LIS variant, DAG .
  • Solution : This problem can be solved using
    •  either an LIS simulation where u first sort the bricks and all their possible orientations by their building criteria then traverse to take the strictly longest increasing sub-building.
    • or a DAG modeling were an edge exists from a brick to another if  it can be built over the other.
  • Gochas :
    • you have to notice that you can actually put two blocks of the same type over each other for example if you re-oriented (10,20,30) to (20,30,10) you can put it underneath. and don’t mind about getting a new one because he mentioned that there are unlimited number of bricks from each type. that’s why we have inserted all possible orientations in our list.
  • Other People Solutions :
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;

struct Block {
	int x, y, z, all[3];
	Block(){}
	Block(int X, int Y, int Z) : x(X), y(Y), z(Z) { all = {x,y,z}; }
};
bool buildable(const Block& a, const Block& b) {
	return ((a.x > b.x) && (a.y > b.y)) || ((a.x > b.y) && (a.y > b.x));
}

bool operator<(const Block& a, const Block& b) {
	for (int i = 0; i < 3; i++){
		if (a.all[i] > b.all[i]) return 1;
		else if (a.all[i] < b.all[i]) return 0;
	}
	return 0;
}
int main() {
	size_t N, x, y, z, i, j, kase=0;
	while (cin>>N && N) {
		vector<Block> v(N);
		while (N-- && cin>>x>>y>>z ) {
			v.push_back(Block(x, z, y)), v.push_back(Block(x, y, z)), v.push_back(Block(y, z, x));
			v.push_back(Block(z, x, y)), v.push_back(Block(y, x, z)), v.push_back(Block(z, y, x));
		}
		sort(v.begin(), v.end());
		int maxL = 0, S[v.size()];
		for (i = 0; i < v.size(); i++) {
			S[i] = v[i].z;
			for (j = 0; j < i; j++)
				if (buildable(v[j], v[i])) S[i] = max(S[i], S[j] + v[i].z);
			maxL = max(maxL, S[i]);
		}
		printf("Case %d: maximum height = %d\n", ++kase, maxL);
	}
	return 0;
}

Extra Testcases:


5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
20
10 19 18
18 19 22
23 33 34
19 21 22
32 32 31
10 90 10
10 80 10
22 22 29
29 28 27
26 25 24
19 80  1
22 21 31
29 28 55
58 42 39
48 78 32
2   2 90
3  99 33
54 44 44
57 13 33
10 29 80
5
1  1  1
1  2  1
1  3  1
1  4  1
1  5  1
5
2  3 100
3  4 200
4  6  50
6  8 100
5  5  75
1
80 90 100
6
15 19 3
44 33 21
88 33 57
31 29 20
99 88 1
52 26 5
2
100 100 100
102  98 100
10
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 26 27
28 29 30
8
10 16 1
5  8  2
20 32 2
10 16 2
16 10 2
32 20 2
8  5  2
16 10 1
0

Output:


Case 1: maximum height = 342
Case 2: maximum height = 588
Case 3: maximum height = 5
Case 4: maximum height = 481
Case 5: maximum height = 180
Case 6: maximum height = 273
Case 7: maximum height = 200
Case 8: maximum height = 310
Case 9: maximum height = 50
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: