Detailed mathematical approach

Problem Summary

Let \(M=50\,515\,093\) and \(s_0=290797\), with the pseudorandom recurrence

$s_{n+1}=s_n^2 \bmod M.$

For a given \(t\), the values are grouped into quadruples

$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$

Each quadruple defines an axis-aligned inclusive rectangle on the grid \(\{0,\dots,M-1\}^2\):

$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$

If \(c_t(x,y)\) is the number of rectangles covering the grid position \((x,y)\), then the displayed clock value is

$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{otherwise.} \end{cases}$

The required total is

$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$

Since \(M^2\approx 2.55\times 10^{15}\), visiting every grid position directly is out of the question. The solution therefore counts whole strips of positions at once.

Mathematical Approach

The core observation is that the final clock display depends only on the coverage count modulo \(12\). That turns the problem into a sweep-line computation over residue classes instead of raw counts.

Step 1: Convert Inclusive Rectangles into Sweep Events

On an integer grid, the inclusive rectangle

$[x_1,x_2]\times[y_1,y_2]$

covers exactly the same grid positions as the half-open box

$[x_1,x_2+1)\times[y_1,y_2+1).$

This reformulation is extremely useful because it means a rectangle starts affecting the sweep at \(x=x_1\) and stops affecting it at \(x=x_2+1\). Thus each rectangle contributes:

$\text{entry event }(x_1,[y_1,y_2],+1),\qquad \text{exit event }(x_2+1,[y_1,y_2],-1).$

If \(x_2=M-1\), then \(x_2+1=M\) lies just outside the grid, so no explicit exit event is needed inside the sweep. Between two consecutive event \(x\)-coordinates, the active set of rectangles is constant, which means the entire vertical strip has a fixed residue distribution along the \(y\)-axis.

Step 2: Compress the \(y\)-Axis

The coverage pattern can change along \(y\) only at rectangle boundaries. Therefore it is enough to keep the sorted distinct breakpoints

$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$

After sorting them as

$Y_0 \lt Y_1 \lt \dots \lt Y_m,$

each elementary interval \([Y_j,Y_{j+1})\) is uniform: for a fixed \(x\)-strip, every active rectangle either covers that whole interval or misses it completely. So instead of tracking individual grid positions, we only need the integer length

$\ell_j=Y_{j+1}-Y_j$

of each compressed interval.

Step 3: Store Only Residues Modulo \(12\)

For any interval \(I\) in the segment tree, let

$L_r(I)=\text{total }y\text{-length inside }I\text{ whose current coverage is }r \pmod{12},\qquad r=0,1,\dots,11.$

Initially no rectangle is active, so every position has residue \(0\). Hence a leaf of length \(|I|\) starts with

$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$

When a rectangle starts on some \(y\)-range, every covered position has its coverage increased by \(1\), so the residue classes rotate:

$L_r'(I)=L_{r-1 \bmod 12}(I).$

When a rectangle ends, the update is \(-1\), which rotates in the opposite direction:

$L_r'(I)=L_{r+1 \bmod 12}(I).$

More generally, an update by \(\Delta\in\{-1,+1\}\) is just

$L_r'(I)=L_{r-\Delta \bmod 12}(I).$

That is why the implementation can use lazy propagation: each pending update is only a cyclic shift of a 12-component vector.

Step 4: Sweep in \(x\) and Accumulate Strip Contributions

Let

$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$

Suppose the next event occurs at \(x=x_{\text{next}}\) and the current sweep position is \(x=x_{\text{cur}}\). The strip width is

$w=x_{\text{next}}-x_{\text{cur}}.$

During this whole strip, the root of the segment tree already knows the current \(y\)-lengths \(L_0,\dots,L_{11}\). Therefore we can add

$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$

After all strips have been accumulated, the clock total is reconstructed by remembering that residue \(0\) is displayed as \(12\):

$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$

Worked Example: A Small \(5\times 5\) Grid

Take a toy grid with coordinates \(\{0,1,2,3,4\}^2\) and two rectangles:

$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$

In half-open form these become

$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$

The \(x\)-events are at \(1,2,4,5\). Now examine the strips:

$[0,1):\quad L_0=5.$

$[1,2):\quad L_1=3,\ L_0=2.$

$[2,4):\quad L_2=2,\ L_1=3.$

$[4,5):\quad L_1=4,\ L_0=1.$

Multiplying by strip widths gives

$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$

$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$

$C_2=2\cdot 2=4.$

All other \(C_r\) are \(0\), and indeed \(8+13+4=25\), the whole grid. The weighted clock sum is

$12\cdot 8+1\cdot 13+2\cdot 4=117.$

This miniature example is exactly what the sweep-line algorithm does on the real input, only with a much larger coordinate range.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they generate the pseudorandom sequence, take every four values as one rectangle, and normalize each rectangle so that the lower and upper coordinates are in sorted order. Then they build two derived datasets: a list of \(x\)-events and a sorted unique list of \(y\)-breakpoints for coordinate compression.

Next, the implementation builds a segment tree over the compressed \(y\)-intervals. Each leaf starts entirely in residue bucket \(0\), because before the sweep every grid position shows \(12\). Every internal node stores the total \(y\)-length in each of the 12 residue classes. A range update does not recompute coverage counts explicitly; it simply rotates the 12 stored totals, and the same rotation is saved as a lazy tag for descendants.

During the sweep, the implementation processes events in increasing \(x\). Before applying the events at the next coordinate, it multiplies the current strip width by the 12 residue lengths stored at the root and adds the results to the global residue totals. It then applies all entry and exit events at that \(x\)-coordinate as range rotations on the affected \(y\)-intervals. After the final event, one last strip up to \(x=M\) is accumulated.

Finally, the implementation converts the residue totals into the required clock sum by giving weight \(12\) to residue \(0\) and weights \(1\) through \(11\) to the remaining residues. The small checkpoints embedded in the implementations are consistent with this derivation, including the trivial case \(t=0\), where the answer is simply \(12M^2\).

Complexity Analysis

Generating the rectangles takes \(O(t)\) time. There are at most \(2t\) sweep events and at most \(2t+2\) distinct \(y\)-breakpoints, so sorting costs \(O(t\log t)\). Each event performs one segment-tree range update in \(O(\log t)\), with only a fixed factor of \(12\) for the residue buckets. Therefore the overall running time is

$O(t\log t),$

and the memory usage is

$O(t).$

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=790
2. Sweep line algorithm: Wikipedia — Sweep line algorithm
3. Segment tree and lazy propagation: cp-algorithms — Segment Tree
4. Modular arithmetic: Wikipedia — Modular arithmetic
5. Half-open interval: Wikipedia — Interval (mathematics)