Problem 732: Standing on the Shoulders of Trolls

Project Euler Problem 732 Solution

EulerSolve provides an optimized solution for Project Euler Problem 732, Standing on the Shoulders of Trolls, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For a fixed $n$, the input is generated deterministically rather than read externally. Each troll contributes a triple $(a_i,b_i,w_i)$: a height contribution, a geometric offset, and a reward. We must choose a subset and an order so that every chosen troll satisfies the standing condition implied by the geometry, while the total reward is maximized. The key observation is that the geometry can be rewritten as an ordinary completion-deadline constraint. After that reduction, the problem becomes a weighted single-machine scheduling problem, which the implementation solves with one-dimensional dynamic programming. Mathematical Approach Let the generated data for troll $i$ be $(a_i,b_i,w_i)$, and let $$A=\sum_{i=0}^{n-1} a_i$$ be the total generated height. The central threshold is $$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$ Step 1: Generate the troll data deterministically The implementations use the modular sequence $$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$ For $i=0,1,\dots,n-1$, the $i$-th troll receives $$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$ So every generated number lies in the interval $[50,150]$, and once $n$ is fixed the whole instance is fixed as well. There is no randomness left in the mathematical problem....

Detailed mathematical approach

Problem Summary

For a fixed $n$, the input is generated deterministically rather than read externally. Each troll contributes a triple $(a_i,b_i,w_i)$: a height contribution, a geometric offset, and a reward. We must choose a subset and an order so that every chosen troll satisfies the standing condition implied by the geometry, while the total reward is maximized.

The key observation is that the geometry can be rewritten as an ordinary completion-deadline constraint. After that reduction, the problem becomes a weighted single-machine scheduling problem, which the implementation solves with one-dimensional dynamic programming.

Mathematical Approach

Let the generated data for troll $i$ be $(a_i,b_i,w_i)$, and let

$$A=\sum_{i=0}^{n-1} a_i$$

be the total generated height. The central threshold is

$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$

Step 1: Generate the troll data deterministically

The implementations use the modular sequence

$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$

For $i=0,1,\dots,n-1$, the $i$-th troll receives

$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$

So every generated number lies in the interval $[50,150]$, and once $n$ is fixed the whole instance is fixed as well. There is no randomness left in the mathematical problem.

Step 2: Compute the geometric threshold with integer arithmetic

Instead of evaluating $\sqrt{2}$ numerically, the implementation computes $\Theta$ as the smallest integer $x$ satisfying

$$2x^2\ge A^2.$$

This is exactly the same as $x\ge A/\sqrt{2}$, hence the smallest such integer is $\lceil A/\sqrt{2}\rceil$. Using only integer comparisons avoids floating-point edge cases and gives identical behavior in all three languages.

Step 3: Convert the standing condition into a deadline

Suppose a chosen troll begins after cumulative occupied height $s$ has already been placed. The geometry encoded by the implementation yields the feasibility inequality

$$A+b_i-s\ge \Theta.$$

Equivalently, the troll must start no later than

$$s\le A+b_i-\Theta.$$

If selecting that troll consumes $a_i$ further units of height, then its completion time is $C_i=s+a_i$. Therefore the same condition can be rewritten as

$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$

So each troll turns into a job with duration $a_i$, reward $w_i$, and completion deadline $d_i$.

Step 4: Sort by deadline and characterize feasible subsets

For a single machine with processing times and deadlines, a chosen subset is feasible if and only if it is feasible when executed in nondecreasing deadline order. This means we do not need to search over all permutations.

After sorting the jobs so that

$$d_1\le d_2\le \cdots \le d_m,$$

a subset is feasible exactly when every chosen prefix finishes on time. If the completion times in that order are $C_1,C_2,\dots$, the required condition is simply

$$C_j\le d_j.$$

Step 5: Dynamic programming over total occupied time

After sorting, let $\mathrm{dp}[t]$ denote the maximum total reward among feasible chosen subsets whose total occupied time is exactly $t$. Initially only time $0$ is reachable.

When we process one job with duration $a$, reward $w$, and deadline $d$, the 0/1 transition is

$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$

The update runs in descending $t$, which prevents the same job from being reused inside one iteration. The final answer is

$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$

Worked Example: $n=5$

The first five generated triples are $(51,55,75)$, $(74,69,145)$, $(121,102,108)$, $(138,86,129)$, and $(142,89,127)$.

Hence

$$A=51+74+121+138+142=526.$$

The threshold is

$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$

because $2\cdot 371^2<526^2\le 2\cdot 372^2$.

The completion deadlines are therefore

$$260,\ 297,\ 377,\ 378,\ 385.$$

The optimal feasible subset is the 2nd, 4th, and 5th trolls. Their total occupied time is

$$74+138+142=354,$$

their total reward is

$$145+129+127=401,$$

and their completion times in deadline order are $74$, $212$, and $354$, which satisfy $74\le 297$, $212\le 378$, and $354\le 385$. This matches the built-in checkpoint.

How the Code Works

The C++, Python, and Java implementations follow the same sequence of steps. First they stream the powers of $5$ modulo $10^9+7$, reduce each term into the interval $[50,150]$, and group every three values into one troll.

Next they sum all generated heights and recover $\Theta$ by integer binary search, so no floating-point square root is needed. Every troll is then converted into a scheduling job with a duration, a reward, and a completion deadline.

The jobs are sorted by increasing deadline, with shorter duration used only as a deterministic tie-breaker. A one-dimensional DP array stores the best reward for each reachable total occupied time, using a large negative sentinel for impossible states. Each job updates that array from right to left, preserving the 0/1 nature of the choice.

After all jobs have been processed, the implementation scans the DP table and returns the largest reachable reward. The algorithmic structure is identical across the three languages; only the surrounding syntax changes.

Complexity Analysis

Let $D=\max_i d_i$. Generating the data and building the job list cost $O(n)$ time. Sorting costs $O(n\log n)$. The dominant part is the dynamic program, which performs a descending time scan up to the relevant deadline for each job, so the total running time is $O(nD)$.

The memory usage is $O(D)$, because only one DP array is kept. Since every generated number lies between $50$ and $150$, the total height $A$ is $O(n)$, and $D$ is also $O(n)$. For this particular generator the practical growth is therefore roughly quadratic in $n$, with linear memory.

Footnotes and References

Problem page: Project Euler 732
Dynamic programming: Wikipedia — Dynamic programming
Knapsack problem: Wikipedia — Knapsack problem
Deadline-ordered scheduling: Wikipedia — Earliest deadline first scheduling
Binary search: Wikipedia — Binary search algorithm

Problem 732 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

namespace {

using i64 = std::int64_t;

constexpr i64 kMod = 1'000'000'007LL;

struct Job {
    int deadline;
    int p;
    int q;
};

int ceil_div_by_sqrt2(const int hsum) {
    const i64 target = static_cast<i64>(hsum) * static_cast<i64>(hsum);
    int lo = 0;
    int hi = hsum;
    while (lo < hi) {
        const int mid = lo + (hi - lo) / 2;
        const i64 lhs = 2LL * static_cast<i64>(mid) * static_cast<i64>(mid);
        if (lhs >= target) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int Q(const int n) {
    std::vector<int> h(static_cast<std::size_t>(n));
    std::vector<int> l(static_cast<std::size_t>(n));
    std::vector<int> q(static_cast<std::size_t>(n));

    i64 pow5 = 1;
    for (int idx = 0; idx < 3 * n; ++idx) {
        if (idx > 0) {
            pow5 = (pow5 * 5LL) % kMod;
        }
        const int r = static_cast<int>(pow5 % 101LL) + 50;
        const int troll = idx / 3;
        if (idx % 3 == 0) {
            h[static_cast<std::size_t>(troll)] = r;
        } else if (idx % 3 == 1) {
            l[static_cast<std::size_t>(troll)] = r;
        } else {
            q[static_cast<std::size_t>(troll)] = r;
        }
    }

    int hsum = 0;
    for (const int x : h) {
        hsum += x;
    }

    const int ceil_h_over_sqrt2 = ceil_div_by_sqrt2(hsum);

    std::vector<Job> jobs;
    jobs.reserve(static_cast<std::size_t>(n));

    int max_deadline = 0;
    for (int i = 0; i < n; ++i) {
        const int start_deadline = hsum + l[static_cast<std::size_t>(i)] - ceil_h_over_sqrt2;
        const int completion_deadline = start_deadline + h[static_cast<std::size_t>(i)];
        jobs.push_back(Job{completion_deadline, h[static_cast<std::size_t>(i)], q[static_cast<std::size_t>(i)]});
        if (completion_deadline > max_deadline) {
            max_deadline = completion_deadline;
        }
    }

    std::sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        if (a.deadline != b.deadline) {
            return a.deadline < b.deadline;
        }
        return a.p < b.p;
    });

    constexpr int kNeg = -1'000'000'000;
    std::vector<int> dp(static_cast<std::size_t>(max_deadline + 1), kNeg);
    dp[0] = 0;

    for (const Job& job : jobs) {
        for (int t = job.deadline; t >= job.p; --t) {
            const int prev = dp[static_cast<std::size_t>(t - job.p)];
            if (prev == kNeg) {
                continue;
            }
            const int cand = prev + job.q;
            if (cand > dp[static_cast<std::size_t>(t)]) {
                dp[static_cast<std::size_t>(t)] = cand;
            }
        }
    }

    int best = 0;
    for (const int v : dp) {
        if (v > best) {
            best = v;
        }
    }
    return best;
}

}  // namespace

int main() {
    assert(Q(5) == 401);
    assert(Q(15) == 941);

    std::cout << Q(1000) << '\n';
    return 0;
}

Python

def ceil_div_by_sqrt2(hsum):
    target = hsum * hsum
    lo = 0
    hi = hsum
    while lo < hi:
        mid = lo + (hi - lo) // 2
        lhs = 2 * mid * mid
        if lhs >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo

def solve():
    kMod = 1000000007
    n = 1000
    
    h = [0] * n
    l = [0] * n
    q = [0] * n
    
    pow5 = 1
    for idx in range(3 * n):
        if idx > 0:
            pow5 = (pow5 * 5) % kMod
            
        r = (pow5 % 101) + 50
        troll = idx // 3
        
        if idx % 3 == 0:
            h[troll] = r
        elif idx % 3 == 1:
            l[troll] = r
        else:
            q[troll] = r
            
    hsum = sum(h)
    ceil_h_over_sqrt2 = ceil_div_by_sqrt2(hsum)
    
    jobs = []
    max_deadline = 0
    for i in range(n):
        start_deadline = hsum + l[i] - ceil_h_over_sqrt2
        completion_deadline = start_deadline + h[i]
        jobs.append((completion_deadline, h[i], q[i]))
        if completion_deadline > max_deadline:
            max_deadline = completion_deadline
            
    jobs.sort(key=lambda x: (x[0], x[1]))
    
    kNeg = -1000000000
    dp = [kNeg] * (max_deadline + 1)
    dp[0] = 0
    
    for deadline, p, job_q in jobs:
        for t in range(deadline, p - 1, -1):
            prev = dp[t - p]
            if prev == kNeg:
                continue
            cand = prev + job_q
            if cand > dp[t]:
                dp[t] = cand
                
    best = max(dp)
    return str(best)

if __name__ == "__main__":
    print(solve())

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Euler732 {
    static final long kMod = 1000000007L;

    static class Job implements Comparable<Job> {
        int deadline, p, q;

        Job(int deadline, int p, int q) {
            this.deadline = deadline;
            this.p = p;
            this.q = q;
        }

        @Override
        public int compareTo(Job other) {
            if (this.deadline != other.deadline) {
                return Integer.compare(this.deadline, other.deadline);
            }
            return Integer.compare(this.p, other.p);
        }
    }

    static int ceilDivBySqrt2(int hsum) {
        long target = (long) hsum * hsum;
        int lo = 0;
        int hi = hsum;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            long lhs = 2L * mid * mid;
            if (lhs >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public static String solve() {
        int n = 1000;
        int[] h = new int[n];
        int[] l = new int[n];
        int[] q = new int[n];

        long pow5 = 1;
        for (int idx = 0; idx < 3 * n; ++idx) {
            if (idx > 0) {
                pow5 = (pow5 * 5L) % kMod;
            }
            int r = (int) (pow5 % 101L) + 50;
            int troll = idx / 3;
            if (idx % 3 == 0) {
                h[troll] = r;
            } else if (idx % 3 == 1) {
                l[troll] = r;
            } else {
                q[troll] = r;
            }
        }

        int hsum = 0;
        for (int x : h) {
            hsum += x;
        }

        int ceilHOverSqrt2 = ceilDivBySqrt2(hsum);

        List<Job> jobs = new ArrayList<>(n);
        int maxDeadline = 0;

        for (int i = 0; i < n; ++i) {
            int startDeadline = hsum + l[i] - ceilHOverSqrt2;
            int completionDeadline = startDeadline + h[i];
            jobs.add(new Job(completionDeadline, h[i], q[i]));
            if (completionDeadline > maxDeadline) {
                maxDeadline = completionDeadline;
            }
        }

        Collections.sort(jobs);

        int kNeg = -1000000000;
        int[] dp = new int[maxDeadline + 1];
        java.util.Arrays.fill(dp, kNeg);
        dp[0] = 0;

        for (Job job : jobs) {
            for (int t = job.deadline; t >= job.p; --t) {
                int prev = dp[t - job.p];
                if (prev == kNeg)
                    continue;
                int cand = prev + job.q;
                if (cand > dp[t]) {
                    dp[t] = cand;
                }
            }
        }

        int best = 0;
        for (int v : dp) {
            if (v > best) {
                best = v;
            }
        }

        return Integer.toString(best);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}