Detailed mathematical approach

Problem Summary

The image has size

$2^N\times 2^N,$

with pixel coordinates \(0\le x,y\le 2^N-1\). A pixel is black exactly when

$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2}. $

So the image is a digital disk centered at \((c,c)\). The quadtree encoding uses:

$\text{uniform block} \Rightarrow 2\text{ bits},\qquad \text{mixed block} \Rightarrow 1+\sum_{i=1}^4 L_i.$

The goal is to compute the total encoding length for \(N=24\) without expanding all pixels.

Mathematical Approach

1) Length depends only on whether a block is uniform. If every pixel in a square block has the same color, the encoder stops immediately and emits a leaf of length \(2\). Otherwise it emits one split bit and recurses into the four children. Since black and white leaves both cost \(2\), we never need to know which color a uniform block has, only whether it is uniform.

2) Reformulate the color test geometrically. For a block

$B=[x_0,x_1]\times [y_0,y_1]$

with integer pixel coordinates, define the squared distance to the center

$D(x,y)=(x-c)^2+(y-c)^2.$

The block is:

$\text{all black if } \max_{(x,y)\in B} D(x,y)\le R^2,$

$\text{all white if } \min_{(x,y)\in B} D(x,y)>R^2.$

Only if neither condition holds is the block mixed.

3) Exact formula for the nearest pixel. The minimum of \(D(x,y)\) over the block is obtained by clamping the center coordinate into the interval of the block:

$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1).$

Then

$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$

This works because \(D(x,y)\) is the sum of two independent convex quadratic functions, one in \(x\) and one in \(y\).

4) Exact formula for the farthest pixel. The maximum of \(D(x,y)\) over an axis-aligned block is always attained at a corner. Therefore we can compute

$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$

and then

$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$

This is exactly what the fast solver uses.

5) Uniformity test. With these two numbers, the recursion decision is immediate:

$d_{\max}^2\le R^2 \Rightarrow \text{all black},$

$d_{\min}^2>R^2 \Rightarrow \text{all white},$

otherwise the circle boundary crosses the block and the block must be subdivided.

6) Recursive length formula. If \(B\) is uniform,

$L(B)=2.$

If \(B\) is mixed and split into \(B_{NW},B_{NE},B_{SW},B_{SE}\), then

$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$

The child order matters for the bitstream but not for the total length. The code uses the order NW, NE, SW, SE.

Worked Examples

Example 1: \(N=1\). The image is \(2\times2\), with \(c=1\) and \(R^2=1\). Among the four pixels, \((1,1)\), \((1,0)\), and \((0,1)\) are black, while \((0,0)\) is white. So the root block is mixed and must split into four \(1\times1\) leaves:

$L=1+4\cdot 2=9.$

Example 2: small checkpoints. The fast method agrees with the brute-force quadtree on

$N=1,2,3,4,5$

and the corresponding lengths are

$9,\ 30,\ 86,\ 212,\ 499.$

These values are a strong sanity check for the geometric pruning logic.

Why the Fast Algorithm Is Correct

The brute-force method explicitly colors every pixel and then compresses. The fast method never builds the bitmap: it replaces “is this block monochrome?” by the exact min/max distance test above. Because those tests are necessary and sufficient, every block is classified exactly as in the brute-force version, so both traversals visit the same logical quadtree and produce the same total length.

Complexity Analysis

The running time is proportional to the number of visited quadtree nodes, not to the total number of pixels \(4^N\). Large regions fully inside or fully outside the disk terminate immediately; only blocks near the circle boundary recurse deeply. Memory usage is just the recursion depth:

$O(N).$

Further Reading

1. Problem page: https://projecteuler.net/problem=287
2. Quadtree: https://en.wikipedia.org/wiki/Quadtree
3. Distance to an axis-aligned box: https://en.wikipedia.org/wiki/Euclidean_distance