Problem 247: Squares Under a Hyperbola

Mathematical Foundation

Theorem 1 (Maximal inscribed square). In a gap with lower-left corner $(x_0, y_0)$ bounded above by $y = 1/x$, the largest axis-aligned square has side length

Proof. A square of side $s$ with lower-left corner $(x_0, y_0)$ fits under the hyperbola iff the upper-right corner $(x_0 + s, y_0 + s)$ satisfies $(x_0 + s)(y_0 + s) \le 1$. The maximal $s$ occurs at equality:

Expanding: $s^2 + s(x_0 + y_0) + x_0 y_0 - 1 = 0$. By the quadratic formula:

Since $x_0 \ge 1$ and $y_0 \ge 0$ with $x_0 y_0 \le 1$, the discriminant $(x_0 - y_0)^2 + 4 > 0$ and $s > 0$. $\square$

Theorem 2 (Binary gap decomposition). Placing a square of side $s$ at corner $(x_0, y_0)$ creates exactly two child gaps:

1. Right gap: lower-left corner $(x_0 + s, y_0)$, inheriting index $(a+1, b)$.
2. Top gap: lower-left corner $(x_0, y_0 + s)$, inheriting index $(a, b+1)$.

No other region under the hyperbola is occluded.

Proof. After placing the square $[x_0, x_0+s] \times [y_0, y_0+s]$, the remaining area under $y = 1/x$ in the original gap splits into:

• The region to the right: $\{(x,y) : x \ge x_0 + s,\; y_0 \le y \le 1/x\}$, with corner $(x_0+s, y_0)$.
• The region above: $\{(x,y) : x_0 \le x \le x_0 + s,\; y_0 + s \le y \le 1/x\}$… but since $(x_0+s)(y_0+s) = 1$, for $x \in [x_0, x_0+s]$ we have $1/x \ge y_0 + s$ iff $x \le x_0 + s$. The top gap extends from $(x_0, y_0+s)$ under $y = 1/x$.

The index of the right gap increments $a$ (one more square to the left), and the top gap increments $b$ (one more square below). $\square$

Lemma 1 (Index pruning). A gap with index $(a, b)$ can produce a descendant with index $(3, 3)$ only if $a \le 3$ and $b \le 3$. Any gap with $a > 3$ or $b > 3$ and all its descendants can be discarded.

Proof. The right child increments $a$, the top child increments $b$. Neither operation can decrease an index component. Hence if $a > 3$, no descendant can have $a = 3$; similarly for $b$. $\square$

Theorem 3 (Greedy ordering correctness). Processing gaps in decreasing order of square side length $s$ produces the squares $S_1, S_2, \ldots$ in the correct greedy order.

Proof. By definition, $S_n$ is the largest square fitting in any remaining gap after $S_1, \ldots, S_{n-1}$ are placed. A max-priority-queue keyed by $s$ extracts this maximum at each step. After extraction, the two child gaps are inserted with their respective $s$-values. Since child gaps always yield strictly smaller squares (the domain shrinks), no future gap can produce a square larger than one already extracted. $\square$

Editorial

We max-heap keyed by square side length. We then initial gap: corner (1, 0), index (0, 0). Finally, generate right child: (x0+s, y0) with index (a+1, b).

Pseudocode

Max-heap keyed by square side length
Initial gap: corner (1, 0), index (0, 0)
while heap is not empty
Generate right child: (x0+s, y0) with index (a+1, b)
Generate top child: (x0, y0+s) with index (a, b+1)

Complexity Analysis

• Time: $O(N \log N)$ where $N$ is the total number of squares processed before the heap is exhausted (or all remaining gaps are pruned). With the $(3,3)$ pruning, $N \approx 782{,}252$. Each heap operation costs $O(\log N)$.
• Space: $O(N)$ for the priority queue.

Answer

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

int main() {
    // Problem 247: Find the largest n such that S_n has index (3,3)
    // Region: 1 <= x, 0 <= y <= 1/x
    // Greedily place largest square first

    auto calcSide = [](double x0, double y0) -> double {
        double diff = x0 - y0;
        return (sqrt(diff * diff + 4.0) - x0 - y0) / 2.0;
    };

    struct Square {
        double side, x, y;
        int left, below;
        bool operator<(const Square& o) const {
            return side < o.side; // min-heap: smallest on top
        }
    };

    priority_queue<Square> pq;
    double s0 = calcSide(1.0, 0.0);
    pq.push({s0, 1.0, 0.0, 0, 0});

    int targetLeft = 3, targetBelow = 3;
    int n = 0, lastN = -1;
    int viable = 1;

    while (viable > 0 && !pq.empty()) {
        Square sq = pq.top();
        pq.pop();
        n++;

        if (sq.left <= targetLeft && sq.below <= targetBelow)
            viable--;

        if (sq.left == targetLeft && sq.below == targetBelow)
            lastN = n;

        // Right child
        double rx = sq.x + sq.side, ry = sq.y;
        double rs = calcSide(rx, ry);
        if (rs > 1e-15) {
            pq.push({rs, rx, ry, sq.left + 1, sq.below});
            if (sq.left + 1 <= targetLeft && sq.below <= targetBelow)
                viable++;
        }

        // Top child
        double tx = sq.x, ty = sq.y + sq.side;
        double ts = calcSide(tx, ty);
        if (ts > 1e-15) {
            pq.push({ts, tx, ty, sq.left, sq.below + 1});
            if (sq.left <= targetLeft && sq.below + 1 <= targetBelow)
                viable++;
        }
    }

    cout << lastN << endl;
    return 0;
}

import heapq
import math

def solve():
    """
    Problem 247: Squares Under a Hyperbola
    Find the largest n such that the index of S_n is (3,3).
    Region: 1 <= x, 0 <= y <= 1/x.
    Greedily place largest squares. Index (left, below) counts squares
    to the left and below.
    """
    def calc_side(x0, y0):
        diff = x0 - y0
        return (math.sqrt(diff * diff + 4.0) - x0 - y0) / 2.0

    # Max-heap via negation: (-side, x0, y0, left, below)
    s0 = calc_side(1.0, 0.0)
    heap = [(-s0, 1.0, 0.0, 0, 0)]

    target_left, target_below = 3, 3
    n = 0
    last_n = -1
    viable = 1  # count of entries in heap with left<=3 and below<=3

    while viable > 0 and heap:
        neg_s, x0, y0, left, below = heapq.heappop(heap)
        s = -neg_s
        n += 1

        if left <= target_left and below <= target_below:
            viable -= 1

        if left == target_left and below == target_below:
            last_n = n

        # Right child
        rx, ry = x0 + s, y0
        rs = calc_side(rx, ry)
        if rs > 1e-15:
            heapq.heappush(heap, (-rs, rx, ry, left + 1, below))
            if left + 1 <= target_left and below <= target_below:
                viable += 1

        # Top child
        tx, ty = x0, y0 + s
        ts = calc_side(tx, ty)
        if ts > 1e-15:
            heapq.heappush(heap, (-ts, tx, ty, left, below + 1))
            if left <= target_left and below + 1 <= target_below:
                viable += 1

    print(last_n)

solve()