CONVERT - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given binary strings S and T, in one move you can swap two characters at distinct indices of S.
Can S be made to equal T after exactly K moves?

EXPLANATION:

First off, we’re only rearranging the characters of S, not adding or removing any new characters.
So, if the counts of 0's and 1's in S and T don’t match, it’s definitely impossible to make them equal.

Let’s call the index i bad if S_i \neq T_i, and good otherwise.
Suppose there are B bad indices initially.
Our goal is to end up with B = 0 after K moves.

Suppose we perform a move on indices i and j. The number of bad indices changes as follows:

  • If S_i = S_j nothing changes.
  • Now, we only think about when S_i \neq S_j.
    • If both i and j are initially bad, after the swap they’ll both become good. B reduces by 2.
    • If i is bad and j is good, after the swap i will become good and j will become bad. B does not change.
    • If i and j are both initially good, after the swap they’ll both become bad. B increases by 2.

So, B can change by +2, 0, or -2 in a single move.

Since we can reduce B by at most 2 in every move, and we’re allowed only K moves, the maximum possible reduction is 2K.
So, if B\gt 2K, the answer is No.

Let’s recap our situation now.
We know that:

  • S and T have an equal number of zeros and ones.
  • B \leq 2K.

In such a situation, the answer is (almost) always Yes!

Why?

There are B bad indices, let them be i_1, i_2, \ldots, i_B.
B must be even, and further, exactly half of these indices will satisfy S_{i_j} = 0, while the other half will satisfy S_{i_j} = 1. (Do you see why?)

Now, perform \frac{B}{2} moves - in each move, choose one bad index that has a 0 and another bad index that has a 1, and swap them.
Both these indices will no longer be bad.
After \frac{B}{2} moves, S will equal T (and since we ensured that B \leq 2K, \frac{B}{2} \leq K meaning we do have enough moves to do this.

Finally, we need to use up the remaining moves, since we must perform exactly K moves.

Now, if N \geq 3 this is quite easy: the string will contain either two zeros or two ones; either way it’ll contain two of the same character so simply keep swapping these two (which doesn’t change the string) till all the moves are used up.

The only potential issue is with N = 2 and S_1 \neq S_2, so we’re forced to swap two different characters.
However, when N = 2, you really only have one possible swap to make at every step, so you can just make all K swaps and check if the resulting string equals T.

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, k; cin >> n >> k;
    string s, t; cin >> s >> t;
    
    int wa = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++){
        if (s[i] == '0' && t[i] == '1'){
            wa++;
        }
        if (s[i] == '1') cnt++;
        if (t[i] == '1') cnt--;
    }
    
    if (cnt != 0){
        cout << "NO\n";
        return;
    }
    
    if (n == 2){
        if (s[0] == s[1]){
            if (s == t){
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        } else {
            if (s == t){
                if (k % 2 == 0){
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            } else {
                if (k % 2 == 0){
                    cout << "NO\n";
                } else {
                    cout << "YES\n";
                }
            }
        }
        return;
    }
    
    if (k >= wa){
        cout << "YES\n";
    } else {
        cout << "NO\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 (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    t = input()
    wrong = 0
    for i in range(n):
        wrong += s[i] != t[i]
    
    if n == 2:
        if k%2 == 0: print('Yes' if s == t else 'No')
        else: print('Yes' if s[::-1] == t else 'No')
    else:
        if wrong%2 == 1 or wrong > 2*k or s.count('0') != t.count('0'): print('No')
        else: print('Yes')
2 Likes
2

I overcomplicated this problem :frowning:

1 Like