Problem 85: Counting Rectangles

Mathematical Foundation

Rectangle Counting

Theorem 1 (Rectangle counting formula). An $m \times n$ grid contains exactly

axis-aligned rectangles.

Proof. An $m \times n$ grid is delineated by $m + 1$ vertical lines $x_0, x_1, \ldots, x_m$ and $n + 1$ horizontal lines $y_0, y_1, \ldots, y_n$. Every axis-aligned rectangle is uniquely determined by a choice of two distinct vertical lines $x_i < x_j$ (for the left and right edges) and two distinct horizontal lines $y_k < y_l$ (for the top and bottom edges). The number of such vertical pairs is $\binom{m+1}{2}$ and the number of horizontal pairs is $\binom{n+1}{2}$. Since these choices are independent, the total count is their product. Expanding:

Verification. For $m = 3$, $n = 2$: $R(3, 2) = \frac{3 \cdot 4}{2} \cdot \frac{2 \cdot 3}{2} = 6 \cdot 3 = 18$. $\checkmark$

Search Space Reduction

Lemma 1 (Upper bound on $m$). We may restrict the search to $m$ satisfying $\frac{m(m+1)}{2} \le T$, i.e., $m \le O(\sqrt{T})$.

Proof. Since $R(m, n) \ge R(m, 1) = \frac{m(m+1)}{2}$ for all $n \ge 1$ (as $\binom{n+1}{2} \ge 1$), once $\frac{m(m+1)}{2} > T$ we have $R(m, n) > T$ for every $n \ge 1$. Moreover, $R$ is strictly increasing in both arguments, so all $m' \ge m$ are likewise infeasible for producing a value closer to $T$ from below. The quadratic inequality $m(m+1)/2 \le T$ yields $m \le \lfloor(-1 + \sqrt{1 + 8T})/2\rfloor = O(\sqrt{T})$. $\square$

Lemma 2 (Optimal $n$ for fixed $m$). For fixed $m$ and target $T$, the unique real root $n^* > 0$ of $R(m, n^*) = T$ satisfies

The optimal integer $n$ is either $\lfloor n^* \rfloor$ or $\lceil n^* \rceil$.

Proof. Setting $R(m, n) = T$ yields $\frac{m(m+1)}{2} \cdot \frac{n(n+1)}{2} = T$, i.e., $n^2 + n - \frac{4T}{m(m+1)} = 0$. By the quadratic formula, the positive root is as stated. Since $R(m, n)$ is strictly increasing in $n$ (for $n \ge 1$), the function crosses the target $T$ between $\lfloor n^* \rfloor$ and $\lceil n^* \rceil$, so one of these two integers minimizes $|R(m, n) - T|$. $\square$

Editorial

The rectangle count factors into one triangular number from the horizontal direction and one from the vertical direction. That is what makes the search manageable: once one side length is fixed, the count becomes a strictly increasing quadratic in the other side.

So instead of testing every pair blindly, we iterate over one dimension and solve for the real value of the other dimension that would hit the target exactly. Because the count is monotone, the best integer width must lie right next to that real root. The candidates are therefore generated by the feasible heights and only a tiny neighborhood around the corresponding optimal width, which turns a two-dimensional search into an essentially one-dimensional one.

Pseudocode

Set the best difference to infinity and the best area to 0.

For each grid height m while its triangular factor does not already exceed the target:
    Compute the real width that would make the rectangle count equal to the target

    Examine the nearby integer widths around that real value
    For each such width:
        compute the exact rectangle count
        compare its distance from the target with the current best
        if it is better, record the new difference and the new area

Return the recorded best area.

Complexity Analysis

Time: $O(\sqrt{T})$. The outer loop runs while $m(m+1)/2 \le T$, giving $m = O(\sqrt{T})$. Each iteration performs $O(1)$ arithmetic.

Space: $O(1)$. Only a constant number of variables are maintained.

Answer

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

int main(){
    // Problem 85: Counting Rectangles
    // R(m,n) = C(m+1,2) * C(n+1,2) = m(m+1)/2 * n(n+1)/2
    // Find area m*n such that R(m,n) is closest to 2,000,000.
    // Answer: 2772

    long long target = 2000000;
    long long best_diff = LLONG_MAX;
    int best_area = 0;

    for(int m = 1; m * (m + 1) / 2 <= target; m++){
        long long tm = (long long)m * (m + 1) / 2;
        double val = 2.0 * target / tm;
        int n = (int)((-1.0 + sqrt(1.0 + 4.0 * val)) / 2.0);

        for(int nn = max(1, n - 1); nn <= n + 2; nn++){
            long long rects = tm * (long long)nn * (nn + 1) / 2;
            long long diff = abs(rects - target);
            if(diff < best_diff){
                best_diff = diff;
                best_area = m * nn;
            }
        }
    }

    cout << best_area << endl;

    return 0;
}

"""
Problem 85: Counting Rectangles

Find the area of the rectangular grid whose rectangle count is
nearest to 2,000,000.

R(m, n) = C(m+1,2) * C(n+1,2) = m(m+1)/2 * n(n+1)/2

Answer: 2772
"""

import math


def solve():
    target = 2_000_000
    best_diff = float('inf')
    best_area = 0

    m = 1
    while m * (m + 1) // 2 <= target:
        tm = m * (m + 1) // 2
        val = 2 * target / tm
        n = int((-1 + math.sqrt(1 + 4 * val)) / 2)

        for nn in range(max(1, n - 1), n + 3):
            rects = tm * nn * (nn + 1) // 2
            diff = abs(rects - target)
            if diff < best_diff:
                best_diff = diff
                best_area = m * nn
        m += 1

    return best_area


def main():
    answer = solve()
    assert answer == 2772
    print(answer)


if __name__ == "__main__":
    main()