Tallest Tower -Editorial ||TTOWER

PROBLEM LINK: Tallest Tower | CodeChef

Problem Code: Tallest Tower | CodeChef

Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef

Contest : Internal Contest CodeChef Adgitm Coding Competition | CodeChef

Author: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

DIFFICULTY:

Easy-Med

PROBLEM:

You are a kid playing with rectangle blocks with sides of length xx and yy and height of 1 unit. Your friend gives you n blocks one by one. You can either accept the block or reject it. You want to stack the blocks such that the blocks form a tall tower. While stacking the blocks you make sure to only accept the block if and only if the block is smaller than the block on top right now. A block is smaller if it fits inside the boundaries of the block currently on top (i.e. doesn’t stick out)
NOTE: You can always reject a block if you want
NOTE: You always stack the blocks such that the height of the tower increases by 1 unit every time

You need to find the maximum height of the tower possible if you already know the blocks which your friend is going to give you and in which order.

SOLUTION:

C++:

int n;
vector<pair<int, int>> arr(1000);

const int MAX = 1005;
vector<vector> memo(MAX, vector(MAX, -1));

int rec(int i, int prev) {
if (i >= n) return 0;
if (memo[i][prev] != -1) {
return memo[i][prev];
}
// check if current rect can be put on top or not
int s1 = arr[prev].first;
int s2 = arr[prev].second;
int p1 = arr[i].first;
int p2 = arr[i].second;
if (max(p1, p2) <= max(s1, s2) && min(p1, p2) <= min(s1, s2)) {
// possible
return memo[i][prev] = max(1 + rec(i + 1, i), rec(i + 1, prev));
} else {
return memo[i][prev] = rec(i + 1, prev);
}
}

int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
arr[i] = {a, b};
}
cout << rec(0, 0);
return 0;
}