Problem 732: Standing on the Shoulders of Trolls

Mathematical Foundation

Lemma 1 (Escape Condition). A troll $i$ standing on top of a pile of total shoulder height $H$ can escape if and only if $H + l_i \ge D_N$. After troll $i$ escapes, the remaining pile height is $H - h_i$.

Proof. Troll $i$ stands on the shoulders of the troll below it, so its feet are at height $H - h_i$ and its shoulders are at height $H$. Its hands reach $H + l_i$. The troll escapes if $H + l_i \ge D_N$. When it leaves the pile, the pile loses $h_i$ in height. $\square$

Theorem 1 (Optimal Escape Ordering). Let $S$ be a set of trolls that can all escape from an initial pile of non-escapees. The optimal order in which trolls escape is by non-decreasing $h_i$: the troll with the smallest shoulder height escapes first.

Proof. Suppose trolls $i$ and $j$ are both escapable, with $h_i < h_j$, and $j$ escapes before $i$. After $j$ escapes, the pile height drops by $h_j$. For $i$ to still escape, we need $H - h_j + l_i \ge D_N$. Had $i$ escaped first instead, the pile drops by $h_i < h_j$, leaving more height for $j$: $H - h_i + l_j \ge D_N$ is easier to satisfy. So escaping the shorter troll first never makes things worse and can make them strictly better. By an exchange argument, sorting by non-decreasing $h_i$ is optimal. $\square$

Theorem 2 (DP Formulation). Let the trolls be sorted by non-decreasing $h_i$. Define the total shoulder height $H_{\text{total}} = \sum_{n=0}^{N-1} h_n$. Process trolls in order of decreasing $h_i$. For each troll, decide: (a) it stays in the pile (contributing $h_i$ to the pile), or (b) it escapes (contributing $q_i$ to the IQ total). The constraint for escape of troll $i$ (the $m$-th troll to escape, with current pile height $H$) is $H + l_i \ge D_N$. This yields a knapsack-like DP on the pile height.

Proof. By Theorem 1, the escape order is fixed once the escape set is chosen. Processing trolls from largest $h$ to smallest, we greedily decide membership. At each step, the pile height $H$ is the sum of $h_j$ for all trolls designated as non-escapees so far. The DP state is $H$, and transitions are: include troll $i$ in the pile ($H \gets H + h_i$) or let it escape if $H + l_i \ge D_N$, adding $q_i$ to total IQ. The optimal solution maximizes total IQ subject to the sequential escape feasibility. $\square$

Editorial

N trolls in a hole of depth D. Maximize total IQ of escapees. A troll can escape from a pile of height H if H + l_i >= D. After escaping, pile height decreases by h_i. We generate troll parameters. We then sort trolls by h in non-decreasing order. Finally, we process the trolls in reverse order with dynamic programming.

Pseudocode

Generate troll parameters
Sort trolls by h in non-decreasing order
DP: process in reverse order (largest h first)
State: pile height H (discretized)
For each troll: pile it or escape it
for each state H in dp
Option 1: troll i stays in pile
Option 2: troll i escapes (if feasible)

Complexity Analysis

• Time: $O(N \cdot H_{\max})$ where $H_{\max} = \sum h_i \approx 100N$, so $O(N^2 \cdot 100) = O(100\,N^2)$. For $N = 1000$, this is $\sim 10^8$ operations.
• Space: $O(H_{\max}) = O(100N)$ for the DP table.

Answer

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

/*
 * Problem 732: Standing on the Shoulders of Trolls
 *
 * N trolls in hole of depth D. Maximize total IQ of trolls that escape.
 * Troll can escape from pile of height H if H + l_i >= D.
 * Greedy: repeatedly escape highest-IQ troll that can reach surface.
 */

const long long MOD_GEN = 1000000007LL;

int main() {
    int N = 1000;
    // Generate parameters
    vector<long long> r(3*N+3);
    r[0] = 1;
    for (int i = 1; i < 3*N+3; i++)
        r[i] = r[i-1] * 5 % MOD_GEN;
    for (int i = 0; i < 3*N+3; i++)
        r[i] = r[i] % 101 + 50;

    vector<int> h(N), l(N), q(N);
    double total_h = 0;
    for (int n = 0; n < N; n++) {
        h[n] = r[3*n]; l[n] = r[3*n+1]; q[n] = r[3*n+2];
        total_h += h[n];
    }
    double D = total_h / sqrt(2.0);

    // Greedy escape
    vector<bool> escaped(N, false);
    double pile_h = total_h;
    int total_iq = 0;

    while (true) {
        int best = -1, best_q = -1;
        for (int i = 0; i < N; i++) {
            if (escaped[i]) continue;
            if (pile_h + l[i] >= D - 0.001 && q[i] > best_q) {
                best_q = q[i];
                best = i;
            }
        }
        if (best == -1) break;
        escaped[best] = true;
        pile_h -= h[best];
        total_iq += best_q;
    }

    printf("Q(%d) = %d\n", N, total_iq);
    return 0;
}

"""
Problem 732: Standing on the Shoulders of Trolls

N trolls in a hole of depth D. Maximize total IQ of escapees.
A troll can escape from a pile of height H if H + l_i >= D.
After escaping, pile height decreases by h_i.
"""

MOD_GEN = 10**9 + 7

def generate_trolls(N):
    """Generate troll parameters using the given PRNG."""
    r = [0] * (3 * N + 3)
    r[0] = 1  # 5^0 mod (10^9+7) = 1
    for n in range(1, 3 * N + 3):
        r[n] = (r[n-1] * 5) % MOD_GEN
    for n in range(3 * N + 3):
        r[n] = (r[n] % 101) + 50

    trolls = []
    for n in range(N):
        h = r[3*n]
        l = r[3*n+1]
        q = r[3*n+2]
        trolls.append((h, l, q))
    return trolls

def compute_D(trolls):
    """Compute hole depth D_N = (1/sqrt(2)) * sum(h_n)."""
    return sum(h for h, l, q in trolls) / (2**0.5)

def solve_Q(N):
    """Find Q(N) = maximum total IQ of escaping trolls."""
    trolls = generate_trolls(N)
    D = compute_D(trolls)

    # Total height of all trolls
    total_h = sum(h for h, l, q in trolls)

    # Greedy approach: try to maximize IQ of escapees
    # A troll can escape if remaining pile height + its arm length >= D
    # After removal, pile shrinks by its shoulder height

    # Sort by some criterion and use DP
    # State: pile height remaining, index
    # Simplified greedy: remove trolls from top, highest IQ first, if they can escape

    # Exact: DP approach
    # Let's enumerate subsets... too expensive for N=1000.
    # Better: sort trolls, use interval DP.

    # Observation: order of escape matters. Troll with smaller h+l should escape later
    # (when pile is shorter). So sort by h+l descending for escape order.

    # Greedy: repeatedly remove the troll that can escape and has highest IQ.
    remaining = list(range(N))
    pile_h = total_h
    total_iq = 0
    escaped = []

    while True:
        best_iq = -1
        best_idx = -1
        for j, i in enumerate(remaining):
            h, l, q = trolls[i]
            # Can troll i escape? Its feet at pile_h - h, hands at pile_h - h + h + l = pile_h + l - h + h = pile_h + l
            # Wait: if troll i is ON TOP of the pile, pile height is pile_h.
            # But troll i is PART of the pile. If i is on top, pile height includes h_i.
            # i's hands reach: (pile_h - h_i) + h_i + l_i = pile_h + l_i
            if pile_h + l >= D - 0.001:  # floating point tolerance
                h, l, q = trolls[i]
                if pile_h + l >= D - 0.001 and q > best_iq:
                    best_iq = q
                    best_idx = j
        if best_idx == -1:
            break
        i = remaining.pop(best_idx)
        h, l, q = trolls[i]
        pile_h -= h
        total_iq += q
        escaped.append(i)

    return total_iq

# Verify
q5 = solve_Q(5)
print(f"Q(5) = {q5}")  # Expected: 401

q15 = solve_Q(15)
print(f"Q(15) = {q15}")  # Expected: 941

q1000 = solve_Q(1000)
print(f"Q(1000) = {q1000}")