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.

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:

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.

Background

Today I gave Atcoder ABC442. In problem E, I observed some analogy of setup of this problem with concepts of Linear Algebra.

Observations

1. Monsters are depicted as vectors in R^2 From Linear Algebra perspective, every monster i at coordinates (xi,yi) is a vector [Xi Yi]^transpose in the vector space R^2.Takahashi stands at the origin (the zero vector). When he faces a monster, he is aligning his "sight vector" with the subspace spanned by that monster's vector.

2. The problem frequently asks if two monsters are in the "same direction." In Linear Algebra, two non-zero vectors u and v are collinear (linearly dependent) if one is a scalar multiple of the other.

3. Quadrant/Basis Partitioning:The space R^2 is divided by the standard basis vectors i = (1,0) and j = (0,1). We can partition the plane into two half-planes (Upper and Lower) based on the sign of the y-component (and x-component if y is 0). This is a rough sort. Or there is Fine Sorting via Determinant: Within the same half-plane, determine the relative order of any two vectors u and v using their determinant (the "cross product").

4. Linear Algebra doesn't naturally have a "start" and "end" for angles like $$$0^\circ$$$ to $$$360^\circ$$$. Instead, partition R^2 into two half-planes (Upper and Lower) to create a strict linear order. Upper Half-Plane: Vectors where y > 0 or (y = 0 and x > 0). Lower Half-Plane: Vectors where y < 0 or (y = 0 and x < 0). Within each half-plane, the determinant uniquely determines the order.

Questions

1. Did anyone find any other way to think about the setup of this problem within space of linear algebra?
2. I saw multiple problems involving graphs and flow between nodes of graphs to be solvable using linear algebra. So far whatever book/blog/pdf of competitive programming I read this approach of thinking in realms of linear algebra in graphs problems is not being formalised. Is there any formalised way to think on this or its not possible?
3. Graphs are non linear data structures in terms of arrangement of nodes so if linear algebra applies to them then it must not deal with arrangement of nodes mostly. May be deal with flow of aggregated values among nodes. Can someone confirm or share his thoughts on this?