PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given two binary strings A and B.
You can modify A as follows:
- Choose L and R (1 \le L \le R \le N) and flip all the elements A_L, A_{L+1}, \ldots, A_R between 0 and 1.
- This has a cost of 1 if A_L = A_R and 0 otherwise.
Find the minimum cost of a sequence of moves that transforms A into B.
Also find a sequence of at most 5000 moves that attains this minimum cost.
EXPLANATION:
From the easy version, we know that the minimum cost is either 0 or 1, with it being 1 only when A and B are of different ‘types’.
We now need to actually need to figure out a sequence of moves.
For now, let’s assume that A and B are both type 3 (i.e. contain both 0 and 1).
We’ll first figure out a 0-cost sequence to convert A to B.
In fact, let’s just ignore B entirely for now.
We work purely on A, and will focus on converting it to the string
00\ldots 001
That is, a string with N-1 zeros followed by a single 1.
That can be done as follows:
- First, sort A in ascending order using adjacent swaps.
That is, repeatedly swap A_i with A_{i+1} while there exists an index i with A_i \gt A_{i+1}.
This takes around \frac{N^2}{4} steps in the worst case since each pair of 1 and 0 can be swapped at most once. - Now, we have a string of the form 000\ldots 0111\ldots 11.
- Operate on the suffix starting at the last 0.
The string becomes 000\ldots 0100\ldots 00, i.e. a string with exactly one 1 in it at some position. - Finally, perform adjacent swaps to move this 1 to the end of the string. This uses at most N more moves.
So, in total we’ve used no more than \frac{N^2}{4} + N + 1 moves to turn A into 00\ldots 001.
Because N \le 50, this is bounded by 1301.
Now, observe that the substring flip operation is self-inverse.
In particular, if we start from a string and perform some sequence of operations; performing that exact same sequence of operations but in reverse will just give us back the original string!
This allows us to then run the exact same algorithm as before but on B instead, which will give us a way of turning B into 00\ldots 001.
Then, reversing this sequence of operations will give us a way to move from 00\ldots 001 to B instead!
Combining both sequences of operations, we’re thus able to transform A to B going via the path
A \to 00\ldots 001 \to B
and using at most 1301+1301 = 2602 operations, which is well within the limit of 5000.
With the above method in hand, it’s not hard to work out the other cases too.
For example, to go from 00\ldots 00 to an arbitrary type 3 string, we can use one operation on 00\ldots 00 to convert it to 00\ldots 001 (this has a cost of 1, and we already know we need 1 cost in this case), after which we can turn 00\ldots 001 into B as above.
The other cases can be worked out similarly, and it’s easy to verify that none of them use more than 2602 moves.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string a, b; cin >> a >> b;
auto type = [] (string s) {
int res = 0;
for (auto c : s) {
if (c == '0') res |= 1;
if (c == '1') res |= 2;
}
return res;
};
if (type(a) != type(b)) cout << 1 << '\n';
else cout << 0 << '\n';
auto go = [&] (string s) {
// turn s into 000...001
vector<array<int, 2>> ops;
while (true) {
bool done = false;
for (int i = 0; i+1 < n; ++i) {
if (s[i] > s[i+1]) {
ops.push_back({i, i+1});
swap(s[i], s[i+1]);
done = true;
}
}
if (!done) break;
}
// now sorted
if (s[n-2] == '1') {
int L = n-2;
while (s[L] == '1') --L;
ops.push_back({L, n-1});
// now at 00..00100..00
for (int i = L; i+1 < n; ++i) ops.push_back({i, i+1});
}
return ops;
};
int ta = type(a), tb = type(b);
if (ta == 1) {
if (tb == 1) cout << 0 << '\n';
else if (tb == 2) {
cout << 1 << '\n';
cout << 1 << ' ' << n << '\n';
}
else {
auto R = go(b);
ranges::reverse(b);
cout << 1 + size(R) << '\n';
cout << n << ' ' << n << '\n';
for (auto [x, y] : R) cout << x+1 << ' ' << y+1 << '\n';
}
}
else if (ta == 2) {
if (tb == 1) {
cout << 1 << '\n';
cout << 1 << ' ' << n << '\n';
}
else if (tb == 2) cout << 0 << '\n';
else {
auto R = go(b);
ranges::reverse(b);
cout << 1 + size(R) << '\n';
cout << 1 << ' ' << n-1 << '\n';
for (auto [x, y] : R) cout << x+1 << ' ' << y+1 << '\n';
}
}
else {
auto L = go(a);
if (tb == 1) {
cout << size(L) + 1 << '\n';
for (auto [x, y] : L) cout << x+1 << ' ' << y+1 << '\n';
cout << n << ' ' << n << '\n';
}
else if (tb == 2) {
cout << size(L) + 1 << '\n';
for (auto [x, y] : L) cout << x+1 << ' ' << y+1 << '\n';
cout << 1 << ' ' << n-1 << '\n';
}
else {
auto R = go(b);
ranges::reverse(b);
cout << size(L) + size(R) << '\n';
for (auto [x, y] : L) cout << x+1 << ' ' << y+1 << '\n';
for (auto [x, y] : R) cout << x+1 << ' ' << y+1 << '\n';
}
}
}
}
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;
auto count = [&](string s){
int cnt = 0;
for (auto x : s) cnt += x == '1';
return cnt;
};
auto f = [&](string s){
int cnt = count(s);
if (cnt == 0) return 0;
else if (cnt < n) return 1;
else return 2;
};
int ca = f(a);
int cb = f(b);
int cost = 0;
vector <pair<int, int>> ans;
auto op = [&](int l, int r){
if (a[l] == a[r]) cost++;
ans.push_back({l, r});
for (int i = l; i <= r; i++) a[i] ^= '0' ^ '1';
};
bool sw = false;
if (ca != cb){
if (ca == 1){
swap(a, b);
sw = true;
swap(ca, cb);
}
if (cb == 1){
op(0, 0);
} else {
op(0, n - 1);
}
}
assert(f(a) == f(b));
while (count(a) < count(b)){
int p = 0;
while (a[p] != '0') p++;
int q = p + 1;
while (a[q] != '0') q++;
while (q != p + 1){
op(q - 1, q);
q--;
}
if (p > 0){
op(p - 1, p + 1);
} else {
while (q + 1 < n && a[q + 1] == '0') q++;
op(q - 1, q + 1);
}
}
while (count(a) > count(b)){
int p = 0;
while (a[p] != '1') p++;
int q = p + 1;
while (a[q] != '1') q++;
while (q != p + 1){
op(q - 1, q);
q--;
}
if (p > 0){
op(p - 1, p + 1);
} else {
while (q + 1 < n && a[q + 1] == '1') q++;
op(q - 1, q + 1);
}
}
for (int i = 0; i < n; i++){
if (a[i] != b[i]){
int p = i;
while (a[p] != b[i]) p++;
while (p != i){
op(p - 1, p);
p--;
}
}
}
assert(0 <= cost && cost <= 1);
cout << cost << "\n" << ans.size() << "\n";
if (sw){
reverse(ans.begin(), ans.end());
}
for (auto [l, r] : ans){
cout << (l + 1) << " " << (r + 1) << "\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;
}