Editorial : Interval Mod
This editorial follows model_sol.cpp: reduce each position to one of two “one-shot” residues, take a baseline independent minimum, then fix a single length-$k$ window by either a uniform $\bmod p$ or a uniform $\bmod q$ on that window.
For each $i$, define
$$ c_0(i)=a_i \bmod p,\quad c_1(i)=(a_i \bmod q) \bmod p,\quad c_{\min}(i)=\min(c_0(i),c_1(i)). $$Let
$$ \text{base}=\sum_{i=0}^{n-1} c_{\min}(i). $$This is the sum if each index could be reduced to its best among the two local options (matching the code’s total_min).
The solution enumerates every contiguous window of exact length $k$. On window $[i,i+k-1]$:
-
If you apply $m=p$ to the whole window, the window contributes $\sum_{j=i}^{i+k-1} c_0(j)$ instead of $\sum_{j=i}^{i+k-1} c_{\min}(j)$, so the total sum is
$$ \text{base} - \sum_{j=i}^{i+k-1} c_{\min}(j) + \sum_{j=i}^{i+k-1} c_0(j). $$ -
If you apply $m=q$ to the whole window, the analogous cost uses $c_1$ in place of $c_0$.
The program computes both costs for every $i$ using prefix sums and takes the global minimum (ans).
- Read the array; compute arrays
c0,c1,cminandbase. - Build prefix sums for
c0,c1,cmin. - For each $i \in [0,n-k]$, evaluate both window formulas; minimize.
Time $O(n)$ per test case, memory $O(n)$.