Unjust Binary Life

The grid sounds dynamic and path-dependent, but the actual trick is that the path is mostly a red herring. Once a path exists, it forces a whole prefix of rows and columns to agree.

Turn cells into equalities

After some flips, call the resulting strings still $a$ and $b$ for convenience. A cell $(i,j)$ has value $0$ iff

$a_i \oplus b_j = 0 \iff a_i=b_j.$

So a valid path is just a bunch of equality constraints between row variables $a_i$ and column variables $b_j$.

Now fix a target $(x,y)$ and suppose some monotone path reaches it.

• If the path moves right from $(i,j)$ to $(i,j+1)$, then both cells must be zero, so $a_i=b_j$ and $a_i=b_{j+1}$. Therefore $b_j=b_{j+1}$.
• If the path moves down from $(i,j)$ to $(i+1,j)$, then $a_i=b_j$ and $a_{i+1}=b_j$. Therefore $a_i=a_{i+1}$.

A monotone path from $(1,1)$ to $(x,y)$ visits every row $1..x$ and every column $1..y$. These constraints are connected through the path, so they force

$a_1=a_2=\cdots=a_x=b_1=b_2=\cdots=b_y.$

That is the whole damn problem. To reach $(x,y)$, all bits in the two prefixes $a[1..x]$ and $b[1..y]$ must become the same bit.

The converse is also immediate: if all those prefix bits are equal, then every cell in the $x \times y$ prefix rectangle is zero, so Yuri can take any monotone path.

So path choice does not matter anymore.

Cost for one cell

Let

• $O_A[x]$ be the number of ones in $a[1..x]$,
• $O_B[y]$ be the number of ones in $b[1..y]$.

In the combined prefixes there are

$\text{ones}=O_A[x]+O_B[y]$

ones, and

$\text{zeros}=x+y-\text{ones}$

zeros.

To make everything equal to $0$, flip all ones. Cost: $\text{ones}$.

To make everything equal to $1$, flip all zeros. Cost: $\text{zeros}$.

Therefore

$f(x,y)=\min(\text{ones},\text{zeros}).$

A direct $O(n^2)$ sum is too slow, because $n$ can be $2\cdot 10^5$.

Rewrite with prefix balances

Define prefix balance as

$d_A[x]=\#1\text{ in }a[1..x]-\#0\text{ in }a[1..x],$

and similarly $d_B[y]$.

For the combined prefixes,

$\text{ones}-\text{zeros}=d_A[x]+d_B[y].$

Also,

$\text{ones}+\text{zeros}=x+y.$

Using

$\min(u,v)=\frac{u+v-|u-v|}{2},$

we get

$f(x,y)=\frac{x+y-|d_A[x]+d_B[y]|}{2}.$

So the answer is

=\frac{\sum_{x=1}^{n}\sum_{y=1}^{n}(x+y)-\sum_{x=1}^{n}\sum_{y=1}^{n}|d_A[x]+d_B[y]|}{2}.$$ The first double sum is easy: $$\sum_{x=1}^{n}\sum_{y=1}^{n}(x+y)=n^2(n+1).$$ Now only this remains: $$T=\sum_{x=1}^{n}\sum_{y=1}^{n}|d_A[x]+d_B[y]|.$$ ## Computing the absolute-value sum Sort all values $d_B[y]$. Also build prefix sums over the sorted array. For a fixed value $u=d_A[x]$, we need $$\sum_y |u+d_B[y]|.$$ The expression $u+d_B[y]$ is negative when $$d_B[y]<-u.$$ So binary search the first position $k$ where $d_B[k]\ge -u$. For the left part, values are negative: $$\sum_{j<k}|u+d_B[j]|=\sum_{j<k}-(u+d_B[j])=-u\cdot k-\text{pref}[k].$$ For the right part, values are nonnegative: $$\sum_{j\ge k}|u+d_B[j]|=u\cdot(n-k)+(\text{pref}[n]-\text{pref}[k]).$$ Add both parts for every $d_A[x]$. Total complexity is $O(n\log n)$ per test case because of sorting and binary searches. The total $n$ over all tests is bounded, so this fits easily. Use `long long`; the answer can be around $n^3$, and `int` will explode like a bad contest hack.