logoChat01.ai

F. Unjust Binary Life time limit per test2 seconds...

Created on: August 10, 2025

Answered using GPT-5 Thinking by Chat01

Question

F. Unjust Binary Life
time limit per test2 seconds
memory limit per test256 megabytes

Yuri is given two binary strings a and b, both of which are of length n. The two strings dynamically define an n \times n grid. Let (i, j) denote the cell in the i-th row and j-th column. The initial value of cell (i, j) has the value of a_i \oplus b_j, where \oplus denotes the bitwise XOR operation. .

Yuri's journey always starts at cell (1, 1). From a cell (i, j), she can only move down to (i + 1, j) or right to (i, j + 1). Her journey is possible if there exists a valid path such that all cells on the path, including (1, 1), have a value of 0.

Before her departure, she can do the following operation for any number of times:

Choose one index 1 \le i \le n, and flip the value of either a_i or b_i (0 becomes 1, and 1 becomes 0). The grid will also change accordingly.
Let f(x, y) denote the minimum required operations so that Yuri can make her journey to the cell (x,y). You must determine the sum of f(x, y) over all 1 \leq x, y \leq n.

Note that each of these n^2 cases is independent, meaning you need to assume the grid is in its original state in each case (i.e., no actual operations are performed).

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains one integer n (1 \le n \le 2 \cdot 10^5).

The second line of each test case contains a binary string a (|a| = n, a_i \in {0, 1}).

The third line of each test case contains a binary string b (|b| = n, b_i \in {0, 1}).

It is guaranteed that the sum of n over all test cases does not exceed 2 \cdot 10^5.

Output
For each test case, output one integer — the sum of minimum operations over all possible cells.

Example
InputCopy
3
2
11
00
2
01
01
4
1010
1101
OutputCopy
5
4
24
Note
In the first test case, the 2 \times 2 grid is shown below.

11 \ 11

In the initial state, Yuri cannot reach any cell.

Yuri can flip a_1 so that the grid becomes:

00 \ 11

and Yuri can travel to cells (1,1) and (1,2).

On the other hand, Yuri can flip b_1 so that the grid becomes:

01 \ 01

and Yuri can travel to cells (1,1) and (2,1).

To move to the cell (2,2), it can be shown that she must perform at least two operations. For example, she can flip both a_1 and a_2 so that the grid becomes:

00 \ 00

Therefore, the answer is 1+1+1+2=5.

give solution in cpp. There should be no comments in the code

Python

python
import random, itertools

def brute(a,b):
    n=len(a)
    # Precompute OA, OB prefix ones
    prefA=[0]*(n+1); prefB=[0]*(n+1)
    for i,ch in enumerate(a,1):
        prefA[i]=prefA[i-1]+(ch=='1')
    for i,ch in enumerate(b,1):
        prefB[i]=prefB[i-1]+(ch=='1')
    # brute compute answer by checking f(x,y)=min operations to set first x A and first y B all equal
    ans=0
    for x in range(1,n+1):
        for y in range(1,n+1):
            oa=prefA[x]; ob=prefB[y]
            f=min(oa+ob,(x-oa)+(y-ob))
            ans+=f
    return ans

def solve(a,b):
    n=len(a)
    OA=[0]*(n+1); OB=[0]*(n+1)
    for i,ch in enumerate(a,1):
        OA[i]=OA[i-1]+(ch=='1')
    for i,ch in enumerate(b,1):
        OB[i]=OB[i-1]+(ch=='1')
    A=[i-2*OA[i] for i in range(1,n+1)]
    B=[j-2*OB[j] for j in range(1,n+1)]
    B_sorted=sorted(B)
    ps=[0]
    for v in B_sorted:
        ps.append(ps[-1]+v)
    tot = 0
    sumB=ps[-1]
    n2=n
    for a in A:
        # find idx where b >= -a
        import bisect
        idx=bisect.bisect_left(B_sorted, -a)
        sum_lt=ps[idx]; cnt_lt=idx
        sum_ge=sumB - sum_lt; cnt_ge=n2 - cnt_lt
        Sa=(sum_ge - sum_lt) + (cnt_ge - cnt_lt)*a
        tot += Sa
    const = n*n*(n+1)//2
    ans = const - tot//2
    return ans, tot%2

for n in range(1,8):
    for _ in range(200):
        a=''.join(random.choice('01') for _ in range(n))
        b=''.join(random.choice('01') for _ in range(n))
        brute_ans=brute(a,b)
        my_ans, parity = solve(a,b)
        if brute_ans!=my_ans or parity!=0:
            print("Mismatch", n, a,b, brute_ans, my_ans, parity)
            raise SystemExit
print("All ok")

Python

python
def fast(a,b):
    n=len(a)
    OA=[0]*(n+1); OB=[0]*(n+1)
    for i,ch in enumerate(a,1):
        OA[i]=OA[i-1]+(ch=='1')
    for i,ch in enumerate(b,1):
        OB[i]=OB[i-1]+(ch=='1')
    A=[i-2*OA[i] for i in range(1,n+1)]
    B=[j-2*OB[j] for j in range(1,n+1)]
    B_sorted=sorted(B)
    ps=[0]
    for v in B_sorted:
        ps.append(ps[-1]+v)
    tot = 0
    sumB=ps[-1]
    n2=n
    import bisect
    for a in A:
        idx=bisect.bisect_left(B_sorted, -a)
        sum_lt=ps[idx]; cnt_lt=idx
        sum_ge=sumB - sum_lt; cnt_ge=n2 - cnt_lt
        Sa=(sum_ge - sum_lt) + (cnt_ge - cnt_lt)*a
        tot += Sa
    const = n*n*(n+1)//2
    return const - tot//2

print(fast("11","00"))
print(fast("01","01"))
print(fast("1010","1101"))

Thought

Finalizing the solution approach

Matches the sample, so sorting with O(n log n) is good. The edge cases are important, especially with n=1 and t up to 1e4, ensuring we sum n ≤ 2e5. I should optimize for fast input/output and print as long long. The user wants minimal code with no comments, so this requires just the code. Let's stick with that.

Writing the C++17 code

For this, I’ll include the necessary headers

Thought for 1m 20s

Answer

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if(!(cin >> t)) return 0;
    while (t--) {
        int n;
        string a, b;
        cin >> n >> a >> b;
        vector<long long> A(n), B(n);
        long long oa = 0, ob = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == '1') ++oa;
            A[i] = (i + 1) - 2 * oa;
        }
        for (int j = 0; j < n; ++j) {
            if (b[j] == '1') ++ob;
            B[j] = (j + 1) - 2 * ob;
        }
        sort(B.begin(), B.end());
        vector<long long> pref(n + 1, 0);
        for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + B[i];
        long long sumB = pref[n];
        long long S = 0;
        for (int i = 0; i < n; ++i) {
            long long aVal = A[i];
            int idx = lower_bound(B.begin(), B.end(), -aVal) - B.begin();
            long long sum_lt = pref[idx], cnt_lt = idx;
            long long sum_ge = sumB - sum_lt, cnt_ge = n - cnt_lt;
            S += (sum_ge - sum_lt) + (cnt_ge - cnt_lt) * aVal;
        }
        long long nn = n;
        long long constant_term = nn * nn * (nn + 1) / 2;
        long long ans = constant_term - S / 2;
        cout << ans << '\n';
    }
    return 0;
}

Share this Q&A