Problem 287: Quadtree Encoding

Mathematical Foundation

Theorem (Quadtree Encoding Length Recurrence). Let $L(x_0, y_0, s)$ be the encoding length of the square region $[x_0, x_0+s) \times [y_0, y_0+s)$. Then

where $Q_1, \ldots, Q_4$ are the four quadrants of size $s/2$.

Proof. By the encoding specification: uniform regions output 2 bits, and mixed regions output 1 bit (the 0 prefix) plus the four sub-encodings. $\quad\square$

Lemma (Uniform Region Tests). For a square $[x_0, x_0+s) \times [y_0, y_0+s)$ and the disk $\{(x,y) : (x-c)^2 + (y-c)^2 \le r^2\}$ with $c = 2^{N-1}$, $r = 2^{N-1}$:

1. The region is entirely black if all four corner pixels $(x_0, y_0)$, $(x_0+s-1, y_0)$, $(x_0, y_0+s-1)$, $(x_0+s-1, y_0+s-1)$ satisfy the disk inequality.
2. The region is entirely white if the pixel in the region closest to the center $(c,c)$ fails the disk inequality. The closest pixel is $(\operatorname{clamp}(c, x_0, x_0+s-1),\, \operatorname{clamp}(c, y_0, y_0+s-1))$.

Proof.

(1) The disk $(x-c)^2 + (y-c)^2 \le r^2$ is a convex set. Since all pixels in the square lie in the convex hull of the four corners, and the four corners are in the disk, all pixels are in the disk. (Formally: a point in the square can be written as a convex combination of the corners; since the disk is convex, any convex combination of points in the disk lies in the disk.)

(2) If the closest point to the center is outside the disk, then every point in the region is at least as far from the center (by the definition of “closest”), hence outside the disk. $\quad\square$

Theorem (Quadtree Complexity for a Disk). The quadtree for a disk of radius $r$ on a $2^N \times 2^N$ grid has $O(2^N)$ nodes.

Proof. Only squares that intersect the boundary of the disk need subdivision. At depth $d$ (squares of side $2^{N-d}$), the circle boundary passes through $O(2^d)$ such squares (the boundary has length $O(r) = O(2^N)$ and each square has side $O(2^N/2^d)$, so the number of boundary-touching squares is $O(2^N / (2^N/2^d)) = O(2^d)$). The total number of internal nodes is $\sum_{d=0}^{N} O(2^d) = O(2^N)$. $\quad\square$

Editorial

We check all-black: all 4 corners inside disk. We then check all-white: closest point outside disk. Finally, mixed: recurse on 4 quadrants.

Pseudocode

Check all-black: all 4 corners inside disk
Check all-white: closest point outside disk
Mixed: recurse on 4 quadrants

Complexity Analysis

• Time: $O(2^N)$ where $N = 24$. The quadtree has $O(2^N)$ nodes, each requiring $O(1)$ work.
• Space: $O(N) = O(24)$ for the recursion stack (depth $N$).

Answer

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

const int N = 24;
const long long C = 1LL << (N - 1);  // center = 2^23
const long long R2 = 1LL << (2 * (N - 1));  // radius^2 = 2^46

bool inside(long long x, long long y) {
    long long dx = x - C;
    long long dy = y - C;
    return dx * dx + dy * dy <= R2;
}

long long solve(long long x0, long long y0, long long s) {
    if (s == 1) {
        return 2;  // single pixel: either 10 or 11
    }

    // Check all four corners of the pixel region [x0, x0+s-1] x [y0, y0+s-1]
    long long x1 = x0 + s - 1;
    long long y1 = y0 + s - 1;

    bool c00 = inside(x0, y0);
    bool c10 = inside(x1, y0);
    bool c01 = inside(x0, y1);
    bool c11 = inside(x1, y1);

    if (c00 && c10 && c01 && c11) {
        // All corners inside => all black (since disk is convex, all interior pixels are inside too)
        return 2;
    }

    // Check if entirely outside: find closest point in the square to center
    long long cx = max(x0, min(C, x1));
    long long cy = max(y0, min(C, y1));
    if (!inside(cx, cy)) {
        // Closest point is outside the disk => all white
        return 2;
    }

    // Mixed: subdivide
    long long h = s / 2;
    return 1 + solve(x0, y0, h) + solve(x0 + h, y0, h) +
               solve(x0, y0 + h, h) + solve(x0 + h, y0 + h, h);
}

int main() {
    long long S = 1LL << N;
    cout << solve(0, 0, S) << endl;
    return 0;
}

"""
Problem 287: Quadtree Encoding

Find the shortest quadtree encoding length for a 2^N x 2^N image (N=24)
where pixel (x,y) is black iff (x - 2^(N-1))^2 + (y - 2^(N-1))^2 <= 2^(2(N-1)).
"""

import sys
sys.setrecursionlimit(1000000)

N = 24
C = 1 << (N - 1)       # center coordinate
R2 = 1 << (2 * (N - 1))  # radius squared

def inside(x, y):
    dx = x - C
    dy = y - C
    return dx * dx + dy * dy <= R2

def solve(x0, y0, s):
    if s == 1:
        return 2

    x1 = x0 + s - 1
    y1 = y0 + s - 1

    # Check if all corners are inside (convexity => all pixels inside)
    if (inside(x0, y0) and inside(x1, y0) and
        inside(x0, y1) and inside(x1, y1)):
        return 2

    # Check if entirely outside: closest point to center
    cx = max(x0, min(C, x1))
    cy = max(y0, min(C, y1))
    if not inside(cx, cy):
        return 2

    # Mixed: subdivide
    h = s // 2
    return (1 + solve(x0, y0, h) + solve(x0 + h, y0, h) +
            solve(x0, y0 + h, h) + solve(x0 + h, y0 + h, h))

def main():
    S = 1 << N
    result = solve(0, 0, S)
    print(result)

if __name__ == "__main__":
    main()