Detailed mathematical approach

Problem Summary

The wall is built on lattice posts inside a \(500\times 500\) square. The quantity to maximize is

$\frac{\text{enclosed area}}{\text{wall length}}.$

By symmetry, the full wall can be reconstructed from one quarter of the boundary, namely a monotone chain from the top midpoint to the right midpoint.

With

$G=250,$

we only optimize a quarter-chain from

$ (0,G)\quad\text{to}\quad (G,0).$

If this quarter-chain has area \(A\) under it and length \(L\), then the full symmetric wall has area \(4A\) and length \(4L\), so the global ratio is exactly

$\frac{4A}{4L}=\frac{A}{L}.$

Mathematical Approach

1) Why one quarter is enough.

The square and the objective are symmetric with respect to both coordinate axes through the center. Therefore an optimal wall can be assumed to be symmetric too. In the first quadrant, its boundary is a chain starting at the top midpoint \((0,G)\) and ending at the right midpoint \((G,0)\).

We may also assume this chain is monotone: \(x\) never decreases and \(y\) never increases. Any backtracking would increase perimeter without helping the enclosed area.

2) Why the chain can be taken convex.

If a local part of the chain bends the wrong way, replacing that dent by its chord increases or preserves the enclosed area while shortening the boundary. So an optimum must be convex in the quarter-square. Convexity means the slopes of successive segments are nondecreasing as we move from the top midpoint to the right midpoint.

3) Primitive step vectors are enough.

A segment from one lattice post to another with displacement

$ (u,v),\qquad u,v\ge 0$

passes through intermediate lattice posts whenever \(\gcd(u,v)>1\). Splitting such a segment at those intermediate posts does not change either its geometric length or the area under it. Therefore we only need primitive vectors

$\gcd(u,v)=1.$

The code includes the axis vectors \((1,0)\) and \((0,1)\) as well, so horizontal and vertical runs are still possible.

4) Coordinate transform used by the DP.

The actual quarter-chain lives in ordinary coordinates \((x,y)\) from \((0,G)\) to \((G,0)\). The implementation stores instead

$j=G-y,$

so the start point becomes \((0,0)\) and the endpoint becomes \((G,G)\). A geometric segment

$ (x,y)\to(x+u,y-v)$

therefore appears in the DP as

$ (x,j)\to(x+u,j+v).$

This is why the code fills `dp[x+u][j+v]` from `dp[x][j]`.

5) Exact area increment of one segment.

The area under one segment is the area of a trapezoid. If the segment goes from height \(y\) down to height \(y-v\) over horizontal distance \(u\), then

$\Delta A=u\cdot\frac{y+(y-v)}{2}=u\left(y-\frac v2\right).$

Since \(y=G-j\), this becomes

$\Delta A=u\left(G-j-\frac v2\right).$

This is exactly what the implementation computes as

$u\left(G-\frac v2\right)-ju,$

which explains the code lines `base_area = u * (GRID - 0.5 * v)` and the later `area_gain -= u` as \(j\) increases.

6) Exact length increment.

The boundary contribution of the segment is simply

$\Delta L=\sqrt{u^2+v^2}.$

So if a quarter-chain is described by a sequence of primitive vectors \((u_i,v_i)\), then

$A=\sum_i \Delta A_i,\qquad L=\sum_i \sqrt{u_i^2+v_i^2}.$

7) Fractional objective and Dinkelbach transform.

The target ratio is

$\rho^*=\max \frac{A}{L}.$

Instead of maximizing a ratio directly, fix a real parameter \(\lambda\) and maximize

$F_\lambda=A-\lambda L.$

For the optimal ratio \(\rho^*\), the maximum value of \(F_{\rho^*}\) is exactly \(0\). This is the standard Dinkelbach principle for fractional programming.

So the algorithm repeatedly solves the easier DP problem for a fixed \(\lambda\), obtains the best chain \((A,L)\), and updates

$\lambda\leftarrow \frac{A}{L}.$

When the update stops changing, we have reached the optimal ratio.

8) DP state and transition.

Let `score[x][j]` be the best value of

$A-\lambda L$

for a convex monotone chain ending at transformed point \((x,j)\), using only directions processed so far.

The vectors are sorted by increasing slope

$\frac vu,$

with \((1,0)\) first and \((0,1)\) last. This enforces nondecreasing slope and therefore convexity.

For one vector \((u,v)\), the transition is

$dp[x+u,j+v]=\max\Bigl(dp[x+u,j+v],\ dp[x,j]+\Delta A-\lambda\Delta L\Bigr).$

Because the update is performed in-place while the current vector is active, the same direction may be used repeatedly. That is exactly what we want for long straight portions of the chain.

9) Why sorting by slope avoids self-intersections.

All chosen segments move rightward and downward in actual coordinates, and their slopes are processed in nondecreasing order. This means the tangent direction of the chain only turns one way. Combined with monotonicity, the quarter-boundary stays convex and cannot self-intersect.

Worked Geometric Interpretation

Suppose the quarter-chain contains a single diagonal step from \((175,250)\) to \((250,175)\), together with the horizontal and vertical parts needed to connect \((0,250)\) to \((250,0)\). This is exactly the kind of “cut off a corner” example described in the problem statement. The DP can represent that chain using repeated \((1,0)\), then one copy of \((75,75)\) split into primitive slope-\(1\) steps, then repeated \((0,1)\).

The area under that chain is the quarter-area of the final enclosed wall, and the quarter-length is the corresponding quarter of the full boundary. The optimization simply searches all such convex monotone quarter-chains and chooses the one with maximum \(A/L\).

Algorithm

1) Build all primitive vectors \((u,v)\) with \(0\le u,v\le G\), plus \((1,0)\) and \((0,1)\).

2) Sort them by slope \(v/u\).

3) For a fixed \(\lambda\), run a DP on the \((G+1)\times(G+1)\) grid of transformed endpoints.

4) Recover the optimal quarter-area \(A\) and quarter-length \(L\) at state \((G,G)\).

5) Update \(\lambda\leftarrow A/L\) and repeat until convergence.

Complexity Analysis

Let \(K\) be the number of primitive directions. One DP solve costs

$O(KG^2)$

time and

$O(G^2)$

memory. The outer Dinkelbach iteration converges in only a small number of rounds, so the full computation is practical.

Checks And Final Result

The C++ program converges to

$132.52756426,$

which is the required maximum area-to-perimeter ratio rounded to eight decimal places.

Further Reading

1. Problem page: https://projecteuler.net/problem=314
2. Fractional programming / Dinkelbach method: https://en.wikipedia.org/wiki/Fractional_programming
3. Primitive lattice vectors: https://en.wikipedia.org/wiki/Coprime_integers