FLIPREV - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given two binary strings A and B, both of length N.
In one move, you can either flip all characters in a substring of A, or reverse a substring of A.
Find a sequence of no more than \left\lceil \frac{N}{2} \right\rceil operations that will result in both strings becoming equal.

EXPLANATION:

There are probably several different ways to achieve this, here’s one of them.

Call an index i bad if A_i \neq B_i. Our aim is to ensure that there are no bad indices in the end.
Note that performing a flip operation on a bad index will make it no longer bad, and vice versa.

We’re allowed to make at most \left\lceil \frac{N}{2} \right\rceil operations.
So, if there are \leq \left\lceil \frac{N}{2} \right\rceil bad indices initially, we can simply perform a single flip operation on each of them individually, and we’ll be done.

What if there are more than \left\lceil \frac{N}{2} \right\rceil bad indices initially?
In this case, first perform the flip operation on the entire string A. This will change all bad indices to not bad and vice versa; so after this operation the number of bad indices will be \lt N - \left\lceil \frac{N}{2} \right\rceil, which is \lt \left\lceil \frac{N}{2} \right\rceil.
We’ve used one operation, and now there are \lt \left\lceil \frac{N}{2} \right\rceil bad indices so we can just use one operation for each of them like the first case.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    string a, b; cin >> a >> b;
    
    int p = 0;
    vector <array<int, 3>> ans;
    while (p < n){
        if (a[p] == b[p]){
            p++;
            continue;
        }
        
        if (p + 1 == n || a[p + 1] == b[p + 1]){
            ans.push_back({1, p, p});
            p++;
            continue;
        }
        
        if (a[p] == a[p + 1]){
            ans.push_back({1, p, p + 1});
            p += 2;
        } else {
            ans.push_back({2, p, p + 1});
            p += 2;
        }
    }
    
    cout << ans.size() << "\n";
    for (auto [type, l, r] : ans){
        l++;
        r++;
        cout << type << " " << l << " " << r << "\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
    
    bad = 0
    for i in range(n):
        bad += a[i] != b[i]
    
    ops = []
    if bad > (n+1)//2: ops.append((1, 1, n))
    for i in range(n):
        if (a[i] != b[i]) ^ (bad > (n+1)//2): ops.append((1, i+1, i+1))
    
    print(len(ops))
    for op in ops: print(*op)
2 Likes
2

I found out that you never need reverse operation, only flip is enough

3 Likes
3

Yes, you can just keep flipping in intervals of bad indices and it works. That’s what I did.

int n; cin >> n;
        string a, b;
        cin >> a >> b;
        int l=0, r=0;
        vector<vector<int>> operations;
        bool equal = a[0] == b[0];
        for(int i=0; i<n; i++) {
            if (a[i] != b[i]) {
                r = i;
                equal = false;
            }
            else {
                if (!equal)
                    operations.push_back({1, l+1, r+1});
                l = r = i+1;
                equal = true;
            }
        }
        if (!equal)
            operations.push_back({1, l+1, r+1});
        cout << operations.size() << "\n";
        for(auto& op: operations) {
            cout << op[0] << " " << op[1] << " " << op[2] << "\n";
        }
1 Like
4

Why’s this code wrong ?

def printOps(a, b):
    ops = []
    for i, (_a, _b) in enumerate(zip(a, b)):
        if _a != _b:
            ops.append(f"1 {i+1} {i+1}")  # Flip single bit
    return ops

def solve():
    n = int(input())
    a = list(input().strip())
    b = list(input().strip())

    limit = (n + 1) // 2  # Correct calculation of ⌈N/2⌉
    
    mismatch = sum(1 for i in range(n) if a[i] != b[i])
    
    if mismatch <= limit:
        ops = printOps(a, b)
        print(len(ops))
        print("\n".join(ops))
    else:
        # Flip the entire string first
        ops = [f"2 1 {n}"]
        a = ['0' if ch == '1' else '1' for ch in a]
        
        # Fix remaining mismatches
        ops += printOps(a, b)

        print(len(ops))
        print("\n".join(ops))

tc = int(input())
for _ in range(tc):
    solve()
5

Line 23 you are doing f"2 1 {n}" instead of f"1 1 {n}"
https://www.codechef.com/viewsolution/1141771485