EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2025
ICPC 2025

J. Stacking Cups

You have a collection of n cylindrical cups, where the ith cup is 2i − 1 cm tall. The cups have increasing diameters, such that cup i fits inside cup j if and only if i < j. The base of each cup is 1 cm thick (which makes the smallest cup rather useless as...

Updated May 21, 2026
Track ICPC
Year 2025
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Time limit 2 seconds

You have a collection of n cylindrical cups, where the ith cup is 2i − 1 cm tall. The cups have increasing diameters, such that cup i fits inside cup j if and only if i < j. The base of each cup is 1 cm thick (which makes the smallest cup rather useless as it is only 1 cm tall, but you keep it for sentimental reasons). After washing all the cups, you stack them in a tower. Each cup is placed upright (in other words, with the opening at the top) and with the centers of all the cups aligned vertically. The height of the tower is defined as the vertical distance from the lowest point on any of the cups to the highest. You would like to know in what order to place the cups such that the final height (in cm) is your favorite number. Note that all n cups must be used. For example, suppose n = 4 and your favorite number is 9. If you place the cups of heights 7, 3, 5, 1, in that order, the tower will have a total height of 9, as shown in Figure J.1.

9
8
7
6
5
4
3
2
1
0
Figure J.1: Illustration of Sample Output 1.

Input

The input consists of a single line containing two integers n and h, where n (1 ≤ n ≤ 2 · 105 ) is the number of cups and h (1 ≤ h ≤ 4 · 1010 ) is your favorite number.

Output

If it is possible to build a tower with height h, output the heights of all the cups in the order they should be placed to achieve this. Otherwise, output impossible. If there is more than one valid ordering of cups, any one will be accepted.

Sample Tests

Sample 1
Sample Input 
4 9
Sample Output 
7 3 5 1
Sample 2
Sample Input 
4 100
Sample Output 
impossible
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • If a cup is placed immediately after a larger cup, it falls into that cup and cannot increase the current total height. So cups that follow a larger cup only ``raise the floor'' for later cups by $1$ each.

  • Therefore every ordering can be rearranged, without changing the final height, into a canonical form: \[ n,n-1,\dots,b+1,\ x_1,x_2,\dots,x_a,\ \text{all remaining cups from }b\text{ down to }1, \] where $1 \le x_1 < x_2 < \dots < x_a \le b$. The first descending block contributes only $n-b$ to the height, and only the increasing subsequence $x_1,\dots,x_a$ can create new maxima.

  • In this canonical form the total height is \[ h = (n-b) + \sum_{i=1}^{a}(2x_i-1) = (n-b) + 2\sum_{i=1}^{a}x_i - a. \] So the problem becomes: choose $b$, choose a size $a$, and choose $a$ distinct numbers from $\{1,\dots,b\}$ with a prescribed sum.

  • For fixed $a$ and $b$, every sum between the minimum $\frac{a(a+1)}{2}$ and the maximum $\frac{a(2b-a+1)}{2}$ is achievable by distinct numbers in $\{1,\dots,b\}$. A simple greedy adjustment from the smallest set $\{1,2,\dots,a\}$ reaches any target in this interval.

Algorithm

  1. The smallest possible height is $2n-1$ (strictly decreasing order), and the largest is $n^2$ (strictly increasing order). If $h$ lies outside this range, answer impossible.

  2. Iterate over every possible $b$. Let \[ t = h - (n-b). \] We now need \[ t = 2\sum x_i - a. \]

  3. For this $b$, choose a candidate size $a$ from the parity and range constraints implied by the observation above. Check whether the required sum \[ \sum x_i = \frac{t+a}{2} \] lies in the attainable interval for $a$ distinct numbers from $\{1,\dots,b\}$.

  4. If it does, build the set greedily: start from $\{1,2,\dots,a\}$ and move elements upward from right to left until the target sum is reached.

  5. Output the canonical order $n,n-1,\dots,b+1,x_1,\dots,x_a,$ then the remaining numbers from $b$ down to $1$.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

Every cup ordering can be transformed into the canonical form above without changing the final height.

Proof.

Whenever a cup follows a larger cup, it cannot create a new maximum height; it only increases the base level inside that larger cup by $1$. Such cups may therefore be postponed past any later cups that do create new maxima, without affecting the moments when the global height increases. Repeating this exchange argument yields a form in which all height-increasing cups appear as one increasing subsequence $x_1<\dots<x_a$, preceded by a descending block of cups larger than $b$ and followed by all remaining smaller cups in descending order. □

Lemma 2.

For a canonical ordering with parameters $b$ and $x_1<\dots<x_a$, the final height is \[ (n-b)+\sum_{i=1}^{a}(2x_i-1). \]

Proof.

The initial descending block $n,n-1,\dots,b+1$ never creates a new maximum after the first cup; it only raises the internal floor by $1$ each time, so it contributes exactly $n-b$. Each cup $x_i$ in the increasing subsequence is the first cup after a smaller one, so it creates a new top, and its contribution above the current floor is exactly $2x_i-1$. The final descending tail again creates no new maximum. Summing these contributions proves the formula. □

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

By Lemma 1, if a height $h$ is achievable at all, then it is achievable by some canonical ordering. By Lemma 2, canonical orderings are in one-to-one correspondence with choices of $b$ and a subset $\{x_1,\dots,x_a\}$ whose sum satisfies the target equation used by the program. The greedy construction produces such a subset whenever the target sum lies in the attainable interval, and the interval characterization is exact for distinct numbers in $\{1,\dots,b\}$. Therefore whenever the algorithm prints an order, that order has height exactly $h$; and whenever the algorithm reports impossible, no canonical representation exists, hence no valid ordering exists at all. □

Complexity Analysis

The algorithm tries all $b$ from $1$ to $n$ once and performs only linear work for the successful construction. Hence the running time is $O(n)$ and the memory usage is $O(n)$.

Implementation Notes

  • The code works with cup indices internally and converts them to actual heights $2i-1$ only when printing.

  • The special impossible case near the maximum height is covered explicitly by the canonical characterization used by the implementation.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

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

long long isqrt_ll(long long x) {
    long long r = sqrt((long double)x);
    while ((r + 1) * (r + 1) <= x) {
        ++r;
    }
    while (r * r > x) {
        --r;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long h;
    cin >> n >> h;

    long long min_h = 2LL * n - 1;
    long long max_h = 1LL * n * n;
    if (h < min_h || h > max_h) {
        cout << "impossible\n";
        return 0;
    }

    for (int b = 1; b <= n; ++b) {
        long long t = h - (n - b);
        if (t < 0) {
            continue;
        }

        long long a = isqrt_ll(t);
        if ((a & 1LL) != (t & 1LL)) {
            --a;
        }
        if (a < 0) {
            continue;
        }

        long long low = a * a;
        long long high = a * (2LL * b - a);
        if (!(low <= t && t <= high)) {
            continue;
        }

        long long need_sum = (t + a) / 2;
        vector<int> inc;
        inc.reserve((size_t)a);
        for (int i = 1; i <= a; ++i) {
            inc.push_back(i);
        }

        long long cur_sum = a * (a + 1) / 2;
        for (int i = (int)a - 1; i >= 0; --i) {
            int max_here = b - ((int)a - 1 - i);
            long long add = min<long long>(max_here - inc[i], need_sum - cur_sum);
            inc[i] += (int)add;
            cur_sum += add;
        }

        vector<int> order;
        order.reserve(n);
        for (int x = n; x > b; --x) {
            order.push_back(x);
        }
        vector<char> used(b + 1, 0);
        for (int x : inc) {
            used[x] = 1;
            order.push_back(x);
        }
        for (int x = b; x >= 1; --x) {
            if (!used[x]) {
                order.push_back(x);
            }
        }

        for (int i = 0; i < n; ++i) {
            if (i) {
                cout << ' ';
            }
            cout << 2LL * order[i] - 1;
        }
        cout << '\n';
        return 0;
    }

    cout << "impossible\n";
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2025/J-stacking-cups/solution.texC++ implementationcompetitive_programming/icpc/2025/J-stacking-cups/solution.cppStatement textcompetitive_programming/icpc/2025/J-stacking-cups/statement.txtStatement PDFcompetitive_programming/icpc/2025/J-stacking-cups/statement.pdfMetadatacompetitive_programming/icpc/2025/J-stacking-cups/meta.jsonYear packetcompetitive_programming/icpc/2025/contest_problems.pdf