Project Euler Problem 790
There is a grid of length and width 50515093 points.
Solution
Answer: 16585056588495119
A standard solution uses a 2D sweep-line with coordinate compression.
Key observations:
- Each update is an axis-aligned rectangle over integer grid points.
- After all $10^5$ updates, a clock showing hour $h$ contributes:
$$h = \begin{cases} 12 & \text{if } k \equiv 0 \pmod{12}\ k \bmod 12 & \text{otherwise} \end{cases}$$
where $k$ is the number of times that grid point was covered.
- So we only need the total area (number of grid points) covered exactly $r \pmod{12}$ times for each residue $r=0,\dots,11$.
Algorithm outline:
- Generate all $4\times 10^5$ pseudorandom values.
- Build the $10^5$ rectangles.
- Convert inclusive ranges into half-open intervals by using $(x_2+1,y_2+1)$.
- Coordinate-compress all x/y boundaries.
- Sweep in x-direction.
- Maintain a segment tree over y that stores, for each node, the total y-length having coverage count congruent to each residue mod 12.
- Rectangle insertion/removal rotates these 12 buckets cyclically.
- Accumulate the area for each residue class and finally compute the weighted sum.
The computation gives:
Answer: 16585056588495119