PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums or binary search
PROBLEM:
You’re given strings A and B of the same length, containing the characters a, b, c.
In one move, you can choose any subsequence of A that’s abc and make it cba.
Can A be turned into B?
EXPLANATION:
Let’s make a couple of observations about the process.
- The
b’s never move from their positions. - The count of each character doesn’t change.
So, if the positions of b’s in A and B don’t match, or the frequencies of their characters don’t match, the answer is immediately No.
Otherwise, note that if A_i \neq B_i at some index, the only possibility is A_i = a and B_i = c, or vice-versa.
Let’s call these (a, c)- and (c,a)-indices respectively.
Let S_1 denote the sorted list of (a,c)-indices, and S_2 denote the sorted list of (c,a)-indices.
Observe that S_1 and S_2 must have the same size, because of the initial conditions that were checked.
Let this common size be k.
Then, the answer is Yes if and only if:
- S_1[i] \lt S_2[i] for each 1 \leq i \leq k; and
- There exists a
bbetween S_1[i] and S_2[i] for each 1 \leq i \leq k.
Proof
Sufficiency should be obvious: if both conditions hold, it’s possible to swap the values at indices S_1[i] and S_2[i] for each i, which will ‘fix’ both those indices. Repeat for every i and A will equal B.
Now, we prove necessity.
First, suppose S_1[i] \gt S_2[i] for some i.
Consider the smallest i for which this happens.
Look at the prefix of A and B of length S_2[i] here. Observe that in this prefix, A will contain exactly one c more than B.
However, our operation can only move c’s left; meaning the number of c’s in this prefix can only increase - so A will always have strictly more c’s in this prefix than B. This means they can never be made equal!
Finally, suppose S_1[i] \lt S_2[i] for every i.
Look at S_1[k] and S_2[k].
- If there’s a
bbetween them, great, swap them and move on to index k-1. - If there’s no
bbetween them, it’s impossible to swap S_1[k] with any element of S_2.
In fact, you can see that if at all S_1[k] can be swapped, it must be with some index that’s greater than S_2[k] (so that abcan exist), but then we know S_1[k] \gt S_2[k] has no solution.
So, if it’s possible to make A = B, there must be abbetween S_1[k] and S_2[k]. Then, move on to the previous indices and apply the same logic.
Checking whether S_1[i] \lt S_2[i] for every i is trivial after building S_1 and S_2.
Checking whether there’s a b between each pair of corresponding indices isn’t hard either: for example, you can use binary search on a sorted list of the b’s, or even prefix sums to count the number of b’s in some range.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
// 2 Years Tribute to Competitive Programming
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s,t;
bool ch = true;
cin >> n>>s>>t;
vl a,b;
set<ll> st;
forl(i,0,n){
if(s[i]=='b'){
if(t[i]!='b'){
yesno(0);
return;
}
st.insert(i);
}
else if(t[i]=='b'){
yesno(0);
return;
}
else{
if(s[i]=='a') c++;
if(t[i]=='a') c--;
if(s[i]!=t[i]){
if(s[i]=='a') a.pub(i);
else b.pub(i);
}
}
}
if(c){
yesno(0);
return;
}
forl(i,0,a.size()){
auto it=st.lower_bound(a[i]);
auto it1=st.lower_bound(b[i]);
if(it==it1 || a[i]>b[i]){
yesno(0);
return;
}
}
yesno(1);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (C++)
// #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;
string ans = "Yes";
vector<array<int, 2>> ac, ca;
int bct = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == b[i]) {
bct += a[i] == 'b';
continue;
}
if (a[i] == 'b' or b[i] == 'b') {
ans = "No";
break;
}
if (a[i] == 'a') ac.push_back({i, bct});
else ca.push_back({i, bct});
}
if (ac.size() != ca.size()) ans = "No";
else {
int k = ac.size();
for (int i = 0; i < k; ++i) {
if (ac[i][0] > ca[i][0] or ac[i][1] == ca[i][1]) ans = "No";
}
}
cout << ans << '\n';
}
}
Thanks dekatin for replying.
