Solution : 
#include <bits/stdc++.h>
#define lli long long
using namespace std;
lli dp[202];
int main()
{
  int t,n;
   lli x,y;
   cin >> t;
   assert(t<=10);
   while ( t-- ) {
      cin >> n;
     assert(n<=200);
       vector < pair<lli,lli> > v;
       for ( int i = 0; i < n; i++ ) {
           cin >> x >> y;
           assert(x<=1000000000);
           assert(y<=1000000000);
           v.push_back(make_pair(x,y));
       }
       sort(v.begin(),v.end());
       dp[0] = v[0].second;
       lli ans = v[0].second;
       for ( int i = 1; i < n; i++ ) {
           dp[i] = v[i].second;
           for ( int j = 0; j < i; j++ ) {
               if ( v[i].second > v[j].second && v[i].first > v[j].first ) dp[i] = max(dp[i], dp[j]+v[i].second);
         }
  ans = max(ans, dp[i]);
       }
       cout << ans << endl;
   }
   return 0;
}
  • Problem Description
    Bob and Alice like to play the game tower of Hanoi. One day Alice challenges Bob to build the tallest tower from a set of disks of different height and radius. The tower of Hanoi can be built by stacking disks on top of each other.

    In order to put disk A on top of disk B, the radius and height of A must be strictly smaller than those of B. Help Bob to win the challenge.

    Input:
    First line of input contains number of test cases T.
    First line of each test case contains value of N, the number of disks. The next N lines contains two positive integer number Ri and Hi corresponding to the radius and height of ith Disk respectively.

    Output:
    For each test case print the maximum height of the tower possible.

    Constraints:
    1<=T<=10
    1<=N<=200
    1<=Ri, Hi<=10^9
  • Test Case 1
    Input (stdin)
  • 2
    3
    4 3
    1 4
    3 2
    5
    5 6
    4 3
    1 2
    7 5
    3 4
    Expected Output
  • 5
    12
  • Test Case 2
    Input (stdin)
  • 4
    3
    2 3
    1 5
    6 4
    5
    1 2
    3 1
    4 5
    6 1
    2 6
    2
    6 1
    4 3
    4
    2 6
    1 4
    4 5
    2 2
    Expected Output
  • 7
    8
    3
    10

The problem described involves helping Bob win a challenge set by Alice in the game "Tower of Hanoi," where they build a tower using disks of varying radii and heights. The goal is to find the maximum possible height of a tower by stacking disks under the following conditions:

Problem Breakdown

  1. Objective:

    • Build the tallest possible tower by stacking disks, where each disk has two properties:
      • Radius (R)
      • Height (H)
    • A disk A can be placed on top of disk B only if both the radius and height of disk A are strictly smaller than those of disk B (i.e., RA<RBR_A < R_B and HA<HBH_A < H_B).

  2. Input:

    • The first line contains the number of test cases T.
    • For each test case:
      • The first line gives N, the number of disks.
      • Each of the next N lines contains two positive integers R (radius) and H (height) for each disk.

  3. Output:

    • For each test case, print the maximum possible height of the tower that can be constructed under the given rules.

  4. Constraints:

    • 1≤T≤101 \leq T \leq 10: Up to 10 test cases.
    • 1≤N≤2001 \leq N \leq 200: Up to 200 disks per test case.
    • 1≤Ri,Hi≤1091 \leq R_i, H_i \leq 10^9: The radius and height of each disk can be as large as one billion.

Solution Explanation

The problem can be modeled as a variant of the Longest Increasing Subsequence (LIS) problem, where we are interested in finding the longest sequence of disks that can be stacked according to the rules (increasing radius and height). The challenge is to maximize the total height of the tower, not just the number of disks.

Step-by-Step Approach

  1. Input Parsing:

    • First, read the number of test cases T.
    • For each test case, read the number of disks N and then the radius R and height H for each disk.

  2. Sorting the Disks:

    • Sort the disks by their radius first and, if radii are equal, by their height. Sorting simplifies the problem because we can now focus on building the tower by comparing heights alone (given that the radii are already in non-decreasing order).

  3. Dynamic Programming (DP) Approach:

    • Let dp[i] represent the maximum height of the tower that can be built ending with the i-th disk.
    • Initialize dp[i] as the height of the disk i because, at minimum, a tower containing only that disk will have a height equal to its own height.
    • For each disk i, check all disks j that came before it (where j<ij < i). If both the height and radius of disk j are smaller than disk i (i.e., Rj<RiR_j < R_i and Hj<HiH_j < H_i), then update dp[i]: dp[i]=max⁡(dp[i],dp[j]+Hi)dp[i] = \max(dp[i], dp[j] + H_i)
    • The result for the test case is the maximum value in the dp array, representing the tallest possible tower that can be built.

  4. Edge Cases:

    • If there is only one disk, the height of the tower is simply the height of that disk.
    • Since the values of RR and HH are quite large (up to 10910^9), ensure that the solution is efficient and avoids unnecessary computations.

Code Explanation


#include <bits/stdc++.h>
#define lli long long
using namespace std;

lli dp[202]; // DP array to store maximum tower heights

int main() {
    int t, n; // t is number of test cases, n is number of disks
    lli x, y; // Variables to store radius and height of a disk
    
    cin >> t; // Read number of test cases
    assert(t <= 10); // Ensure the number of test cases is within the constraints
    
    while (t--) {
        cin >> n; // Read number of disks for this test case
        assert(n <= 200); // Ensure number of disks is within the limit
        
        vector<pair<lli, lli>> v; // Vector to store (radius, height) pairs of disks
        
        for (int i = 0; i < n; i++) {
            cin >> x >> y; // Read radius and height of each disk
            assert(x <= 1000000000); // Ensure radius is within the constraint
            assert(y <= 1000000000); // Ensure height is within the constraint
            v.push_back(make_pair(x, y)); // Store disk properties as a pair
        }
        
        // Sort the disks first by radius, then by height
        sort(v.begin(), v.end());
        
        dp[0] = v[0].second; // The tallest tower using just the first disk
        lli ans = v[0].second; // Keep track of the maximum tower height
        
        // Iterate over each disk
        for (int i = 1; i < n; i++) {
            dp[i] = v[i].second; // Initialize dp[i] as the height of the i-th disk
            
            // Check previous disks to see if they can be stacked under the i-th disk
            for (int j = 0; j < i; j++) {
                // If both radius and height of disk j are smaller than those of disk i
                if (v[i].second > v[j].second && v[i].first > v[j].first) {
                    dp[i] = max(dp[i], dp[j] + v[i].second); // Update dp[i]
                }
            }
            
            // Update the maximum tower height found so far
            ans = max(ans, dp[i]);
        }
        
        // Output the result for the current test case
        cout << ans << endl;
    }
    
    return 0;
}

Key Points of the Code:

  • Sorting: The disks are sorted based on their radius and height to simplify the problem of finding a valid stacking sequence.
  • Dynamic Programming: The dp[i] array is used to store the maximum height of the tower that can be formed ending with the i-th disk.
  • Complexity: The time complexity is O(N2)O(N^2) per test case due to the nested loops, which is feasible for N≤200N \leq 200.

Example Walkthrough

Test Case 1:

Input:


2
3
4 3
1 4
3 2
5
5 6
4 3
1 2
7 5
3 4

For the first test case with 3 disks:

  • Disk 1: R=4,H=3R = 4, H = 3
  • Disk 2: R=1,H=4R = 1, H = 4
  • Disk 3: R=3,H=2R = 3, H = 2

The optimal stack is Disk 3 on top of Disk 1, resulting in a total height of 55 (3 + 2).

For the second test case with 5 disks:

  • After sorting and applying the DP algorithm, the maximum tower height is 1212.

The outputs for these two test cases are 5 and 12, respectively.