# PROBLEM LINK:

Author: iceknight1093
Tester: wasd2401
Editorialist: iceknight1093

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 b between 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 b between them, great, swap them and move on to index k-1.
• If there’s no b between 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 a b can 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 a b between 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';
}
}

1 Like

Can someone help me understand which test case will fail this?

https://www.codechef.com/viewsolution/1053233950

can someone explain which testcase this will fail?
https://www.codechef.com/viewsolution/1053199588

1 Like

I solved this by having two counters, one temporary, operating on them based on current character.

https://www.codechef.com/viewsolution/1053187780

Hello, I need a little help regarding the solution given in editorial. I hope you can help me out since you solved it. I am basically confused which edges cases am I missing out in this code❌ :-

https://www.codechef.com/viewsolution/1053299951

The above code uses the same logic as the editorialist’s code, tried that code too and it ran fine✔.

https://www.codechef.com/viewsolution/1053296990

I am really confused but can’t get the edges cases where it failed, please help me!!!

1
4
abbc
aabc

Your code prints “YES” for this case

1 Like

Thanks dekatin for replying.

This thing had been bugging me from long. I forgot to check the case when a[i] has ‘b’ but b[i] has no ‘b’.

Well do you have any idea regarding how to get these edge cases?

In 209 and 210, you are checking if b in B and not in A. You need to check when b in A and not in B.

1 Like

Hi @anup

Your code fails on

1
5
aabcc
ccbaa

1 Like

Thanks got it!

Can you recommend me any technique to get these edge cases while coding or is random testing and test case generator code the only way to detect??

Should we take just the first occurrence of abc or any abc works? for example in string “bbcaccbaaccabc” shall we take bbcAccBaaCcabc or bbcaccbaaccABC? (caps are just to represent selections)

can someone explain which test case is failed here CodeChef: Practical coding for everyone

Sure!

Although you are a 3*, I guess you may have better technics.

Mosty, I try to make inferences from the setting iftself, and sample test cases (which almost everytime are choosen to show be more amount or significant corner cases). But the core of my approach is handling them separately.
If I don’t consider something, and got WA, I just need to change little things, and not change the whole logic.

I tend to set my logic based in the max amount of edge cases I can think of. This is, in this problem, there were these:

• There has to be the same amunt of ‘a’, ‘b’ and ‘c’ in both arrays
• The ‘b’ have to be in the same index in both.
• There can’t be a A[i] == ‘c’ && B[i] == ‘a’ before at least one A[i] == ‘a’ && B[i] == ‘c’
• There has to be a b between every (A[i] == ‘a’ && B[i] == ‘c’) and (A[i] == ‘c’ && B[i] == ‘a’)

Note how they are very related, but not actually the same. Being super clear on your corner cases and constraints helps me to modify them easierly.

I actually spotted everything during the contest, but I couldn’t think of a way to solve the last two
(I knew I should’ve used prefix sum, but I didn’t realized a way until very after)

I set my logic using the some principles of “Database normalization”

1. Values stored in a column should be of the same domain.
2. It should not have Partial Dependency .
3. It doesn’t have Transitive Dependency.

But instead, I fix them to this:

1. Variables and Data Structures should be related to the corner case (avoid mixing them)
2. If possible, corner cases should be handled separately
3. If possible, the use of Variables and Data Structures should be only be modified according to their corner case. They can be read by any corner case, but not modifed (make a copy instead)

Why? Because if I didn’t consider a corner case or did it wrongly, I only need to modify an specific code part, not the logic itself.

That being said. This is how I solved the problem (the submission is recent because I made one to be clear in what I try to say)
Solution: 1053395300 (codechef.com)

And this was my first right attempt. It’s more messy, but follows the same logic:
Solution: 1053300719 (codechef.com)

1 Like

On lines 200 to 204 and 209, you are not handling right the A[i] != ‘b’ && B[i] ==‘b’ situtaion. It should be considered a reason to break into a “No”, but you are pushing them into ma or mc, making an undefined behaviour.

So this case is passed as a “Yes”:
1
3
abc
bbb

Thanks @ulisesaugusto1 for detailed explanation of approach😍.

I actually did not know the concept of normalization before. The things I learn :-

1. Being super clear on your corner cases and constraints helps me to modify them easily which I sometimes mess up in hurry to submit which needs to be improved on my part.

2. If possible, corner cases should be handled separately which I did not do but can be done to be clear on my part.

Well I did get the queue implementation upon dry run, still I am taking a little while to sink in the concept😅.

That was an awesome explanation on how to consider edge cases one at a time, I will definitely follow it orz.

[NOTE :- I recently got promoted to 3⭐ after this contest , maintaining it is a challenge actually😥, but the improvements and concept you have best wishes from my side on becoming a 3⭐ soon]

Happy CPing😎

1 Like

queue is the FIFO DS (First In, First Out, Date Structure). Think of this like any line to buy something. If you arrive first, you should order first.

It’s opposed to stack (LIFO) (Last In, First Out). This is like a pile of stones. If you put many stones as a pile, you can’t touch the first you put. You need to take out the last stone you put.

Why to choose this DA?
Every a_c needs to be paired with an c_a. I understand editorial’s approach, but I personally don’t think it’s intuitive, specially in an under-peasure contest. I understand the comparing lower index approach, but I don’t think people will catch that at first sight.

Don’t knowing the answer, the most likely approach is to spot that a a_c needs a pair. As simple as that. If a pair is made with a ‘b’ in the middle, then that a_c is not available anymore.

To this point, it implies you need a vector to push and pop the available a_c. But what a_c should we take from many available?

Due we need to have a ‘b’ in the middle, there’s a risk of to not have one. Let’s reduce the risk by choosing the farthest a_c (more distance, less risk). So, a queue is better option than a vector. The farthest will always be the first a_c to be put in.

That’s why I chose a queue.
I’m not saying editorial’s approach is wrong. Actually, I would admire anyone who could conclude the index thing. I’m just saying it’s not intuitive to a person who don’t know the answer and it’s trying to spot patterns.

Also, I watched you solved your code and implemented my advice. I can’t word how flattered I feel.

1 Like

I just read through your code and the condition for checking 'b’s looked very sus, so it was just experience I guess

There is such a thing as stress-testing, but that takes a lot of time to be viable in live contest imo.

Also there are debuggers on programs like VScode, but I also have 0 experience with that.

Some videos on the topic if you are interested:

2 Likes

I had seen one of the videos you mentioned before, problem I face is writing a brute approach or checker function, I get stuck in that, writing a batch script in windows to run both is fine but getting the brute feels more complicated🤔

As you mentioned time is a factor I agree and getting the brute and then stress testing does take long rather guessing edge cases based on experience is better.

Ya, we need to select b for a in a_c and c in c_a such that the b’s index is minimal(to be risk free, this is valid condition) as possible to satisfy the case that b must lie between a and c. First in first out equivalent to indexing from 0 till n in increasing order checking.

Hi! I’ve considered this similar to the parentheses matching problem, with the constraint that the matching brackets must have a content in between, which in this case is a ‘b’.
Opening bracket means: a[i] = ‘a’ and b[i] = ‘c’.
Closing bracket means: a[i] = ‘c’ and b[i] = ‘a’.
Content means: a[i] = ‘b’ and b[i] = ‘b’.

I’ve tried the following cases apart from the given tests and my code works as expected:

6
ababcc
cbcbaa
5
aabcc
ccbaa
5
ababc
cbcba


Still, the code is failing on actual. Could anyone please hint at which test case this might be failing?

Submission: CodeChef: Practical coding for everyone

Thanks!