Background↵
==================↵
↵
Today, I gave Atcoder ABC 443 and found the last problem interesting to write this blog for. Here is the link of [Problem G](https://atcoder.jp/contests/abc443/tasks/abc443_g). ↵
↵
Objective↵
==================↵
↵
I approached this problem using the standard Euclidean floor-sum algorithm. To approach this problem beyond the standard Euclidean floor-sum algorithm, we can view it as a setup of some Geometry and calculus.↵
↵
1. The Geometric Interpretation↵
==================↵
↵
The condition X[k]>k describes a relationship between a line and the boundaries of the modulo operator. Let f(k)=Ak+B. The modulo operation effectively "cuts" the line y=f(k) every time it hits a multiple of M and shifts it down. If we plot the points (k, X[k]), they lie on a series of parallel line segments with slope A. The condition X[k]>k asks: "Which of these points lie above the identity line y=k?"↵
↵
2. Calculus Approximation↵
=========================↵
↵
While the problem is discrete, we can use calculus-inspired reasoning to approximate the answer.↵
↵
Consider the continuous version:↵
$$\int_{0}^{N} \mathbb{1}_{\{(Ax+B \pmod M) > x\}} dx$$↵
↵
Because the modulo function is periodic, the value (Ax+B) (mod M) behaves like a uniform distribution U(0,M) over long intervals if gcd(A,M)=1.↵
The Probability Approach: At any point k, the probability that a random value in [0,M) is greater than k is (M-1-k)/M. The Expected Value: Ans is approx. equal to summation from k = 0 to N-1 of (M-1-k)/M = (1/M)*(N*(M-1)-((N-1)*N)/2↵
↵
For the sample case N=443, M=2026, A=131, B=210, this formula gives approx. 394.3, which is remarkably close to the actual answer of 395. This suggests that for large N, the answer is dominated by the density of the line rather than the "jitter" of the modulo.↵
↵
↵
If you have any other mental model to think of this problem, comment below ideas.
==================↵
↵
Today, I gave Atcoder ABC 443 and found the last problem interesting to write this blog for. Here is the link of [Problem G](https://atcoder.jp/contests/abc443/tasks/abc443_g). ↵
↵
Objective↵
==================↵
↵
I approached this problem using the standard Euclidean floor-sum algorithm. To approach this problem beyond the standard Euclidean floor-sum algorithm, we can view it as a setup of some Geometry and calculus.↵
↵
1. The Geometric Interpretation↵
==================↵
↵
The condition X[k]>k describes a relationship between a line and the boundaries of the modulo operator. Let f(k)=Ak+B. The modulo operation effectively "cuts" the line y=f(k) every time it hits a multiple of M and shifts it down. If we plot the points (k, X[k]), they lie on a series of parallel line segments with slope A. The condition X[k]>k asks: "Which of these points lie above the identity line y=k?"↵
↵
2. Calculus Approximation↵
=========================↵
↵
While the problem is discrete, we can use calculus-inspired reasoning to approximate the answer.↵
↵
Consider the continuous version:↵
$$\int_{0}^{N} \mathbb{1}_{\{(Ax+B \pmod M) > x\}} dx$$↵
↵
Because the modulo function is periodic, the value (Ax+B) (mod M) behaves like a uniform distribution U(0,M) over long intervals if gcd(A,M)=1.↵
The Probability Approach: At any point k, the probability that a random value in [0,M) is greater than k is (M-1-k)/M. The Expected Value: Ans is approx. equal to summation from k = 0 to N-1 of (M-1-k)/M = (1/M)*(N*(M-1)-((N-1)*N)/2↵
↵
For the sample case N=443, M=2026, A=131, B=210, this formula gives approx. 394.3, which is remarkably close to the actual answer of 395. This suggests that for large N, the answer is dominated by the density of the line rather than the "jitter" of the modulo.↵
↵
↵
If you have any other mental model to think of this problem, comment below ideas.
