EQINV - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

Observation

PROBLEM:

Given two binary strings A and B, in one move you can either flip one character of A, or reverse A.
Using at most \left\lceil \frac{N}{2} \right\rceil moves, make A and B have the same number of inversions.

EXPLANATION:

There can be several strings with the same number of inversions as B, so we need to decide which one of them to convert to.

One simple case is B itself: if we can convert A to B within \left\lceil \frac{N}{2} \right\rceil moves, that obviously gives us a solution. One trivial way to do this is to simply flip all those positions that differ in A and B.

Unfortunately, this is not always possible: a simple example is when A = 0000\ldots 000 and B = 1111\ldots 1111, when you need N moves no matter what.

However, this gives us a starting point. Suppose we can’t convert A to B using our trivial algorithm. Then, we know for sure that A and B differ at \gt \left\lceil \frac{N}{2} \right\rceil positions — in other words, they match at \lt \left\lceil \frac{N}{2} \right\rceil positions. Let’s try to use this to our advantage.

For a binary string S, let rev(S) denote the reverse of S, and flip(S) denote the string where we flip every character of S. What can you say about the number of inversions of rev(S) and flip(S)?

Answer

They are equal!

A simple proof is to look at some pair of positions (i, j) with i \lt j.

  • If S_i = S_j, then (i, j) doesn’t contribute to an inversion in flip(S) and (N+1-j, N+1-i) isn’t an inversion in rev(S)
  • If S_i \lt S_j, then (i, j) is an inversion in flip(S) and (N+1-j, N+1-i) is an inversion in rev(S)
  • If S_i \gt S_j, then (i, j) is not in inversion in flip(S) and (N+1-j, N+1-i) is not an inversion in rev(S)

This gives us a bijection between inversions in flip(S) and rev(S), so they are equal in number.

Now, let’s go back to our initial solution. Since A and B match at \lt \left\lceil \frac{N}{2} \right\rceil positions, A and flip(B) differ at \lt \left\lceil \frac{N}{2} \right\rceil positions, which means we can easily convert A to flip(B) and have at least one move remaining.

Then, from the discussion above, note that rev(flip(B)) has the same number of inversions as rev(rev(B)). rev(rev(B)) is, however, just B.

So, using our one remaining move to reverse the string converts A to rev(flip(B)), which has the same number of inversions as B, and we are done.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0, F = 0, S = 0;

void solve()
{
    int n = readIntLn(1, 1e5);
    sumN += n;
    string a = readStringLn(n, n);
    string b = readStringLn(n, n);
    assert(*min_element(a.begin(), a.end()) >= '0' and *max_element(a.begin(), a.end()) <= '1');
    assert(*min_element(b.begin(), b.end()) >= '0' and *max_element(b.begin(), b.end()) <= '1');
    int dif = 0;
    for(int i = 0; i < n; i++)
        dif += a[i] != b[i];
    vector<pii> ops;
    if(dif <= (n + 1) / 2)
    {
        for(int i = 0; i < n; i++)
        {
            if(a[i] != b[i])
                ops.push_back({1, i + 1});
        }
        F++;
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            if(a[i] == b[i])
                ops.push_back({1, i + 1});
        }   
        ops.push_back({2, -1});
        S++;
    } 
    cout << sz(ops) << endl;
    for(auto &[type, i]: ops)
    {
        cout << type;
        if(type == 1)
            cout << " " << i;
        cout << endl;
    }
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1e5);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    readEOF();
    assert(sumN <= 2e5);
    cerr << "First type cases: " << F << endl;
    cerr << "Second type cases: " << S << endl;
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	mismatches = 0
	for i in range(n):
		mismatches += a[i] != b[i]
	if mismatches <= (n+1)//2:
		print(mismatches)
		for i in range(n):
			if a[i] != b[i]: print(1, i+1)
	else:
		print(1 + n - mismatches)
		for i in range(n):
			if a[i] == b[i]: print(1, i+1)
		print(2)
1 Like