 # CCD - Editorial

Author: Arpit Kesharwani
Tester: Anshu Garg
Editorialist: Arpit Kesharwani

EASY

# PROBLEM:

Given two strings A, B and Q queries, for each query we have to choose substring A[L...R] and see if it is possible it to convert to B[L..R] by cyclically incrementing two consecutive characters of A[L…R].

# EXPLANATION:

Each query can be solved in O(R-L) as:
For query: L, R.
We will iterate over the substring from lowest to highest index and use the operation on [i,i+1] to change A[i] = B[i] for i \lt R.
If the last character A[R] becomes equal to B[R] after doing above operations the answer is YES else it is NO.

The above process of updating at each index and be mathematically expressed as:
Let C_i = B_i - A_i, be the number of operations to convert A_i to B_i if increasing single character were allowed.
Also for each query let’s define D_i as the number of operation we apply at index i.
Then, mathematically D_i = C_i - D_{i-1} as after applying D_{i-1} operation on index i-1, A_i changes to A_i + D_{i-1}, so to make it equal to B_i we do B_i - (A_i + D_{i-1}) operations on i^{th} index.

So, we get the value of D_R as:
D_R = C_R - C_{R-1} + C_{R-2} + .... (-1)^{R-L} C_L
As we cannot apply any operation at R^{th} position so if we want substrings to be equal D_R must be 0. Therefore the alternating sum of C_i in range L to R must be zero modulo 26 for answer to be YES .
Modulo 26 is required because operations are cyclic with length 26, as applying the same operation to an index 26 times, results in the same result. So, if D_R = 26\cdot p + t (where t is the remainder of D_R modulo 26), then applying operation at R, D_R times is same as applying operation at R, t times.

# SOLUTIONS:

Setter's Solution
#include<iostream>

using namespace std ;

int main() {
int test_cases ;
cin >> test_cases ;
long long sum_n = 0, sum_q = 0;
for(int test_case = 1; test_case <= test_cases; ++ test_case) {
int n, q; cin >> n >> q;
string a, b; cin >> a >> b;
int E[n+1]; E = 0;
for(int i=1;i<=n;++i) {
int c = (b[i-1]-a[i-1]+26)%26;
E[i] = E[i-1];
if(i%2 == 0) E[i] += c;
else E[i] -= c;
}

while(q--) {
int l,r; cin >> l >> r;
if((E[r]-E[l-1])%26) cout << "NO\n";
else cout << "YES\n";
}
}
}

4 Likes

Nicely explained.
Is Tester’s solution code missing? I can only see “indent whole code by 4 spaces” in that dropdown.

I suspect that author is joking.

4 Likes It does seem that way in the first look, but I have also noticed the same lines in place of the missing solution codes of some other Div 2 problem editorials of this contest as well. Maybe they wanted to replace this template line with the actual finalized codes, but mistakenly missed expanding the details dropdown in the preview and so has been published in error.

1 Like

We must get to bottom of this.

1 Like
for (int i = 0; i < n; i++) {
int x = (a.charAt(i) - 'a');
int y = (b.charAt(i) - 'a');
del[i] = ((y - x) % 26 + 26) % 26;

}

for (int i = 0; i < m; i++) {
int l = sc.nextInt() - 1;
int r = sc.nextInt() - 1;

int diff = 0;

for (int j = l; j <= r; j++) {
diff = (del[j] - diff + 26) % 26;
}

if (((diff % 26) == 0) || (l == r))
sb.append("YES");
else
sb.append("NO");


My approach is same but still I’m getting WA,I am unable to understand where I’m going wrong, please ignore the high complexity,I just want to where I’m going logically wrong !. Thank You,

Here what i didn’t understand was that in a querie am i eligible to use the elements outside the rangeor not

3 Likes

Well, the statement is incomplete. It should be mentioned that in a query, for a given [L, R], we can perform a move at an index i iff i\in[L, R).

6 Likes

I think this approach is giving TLE, or can any tell me how to apply this approach without TLE or any other approach for this question please.

The last equation missed C_R ?

well i also have the same question
otherwise it will fail on this test case
1
5 1
abcde
bfgff
2 4
if we consider i∈[L,R] then ans==“YES”
otherwise ans ==“NO”
PS: please try to give more clear statement in question

1 Like

I did not understand the last statement.

As we cannot apply any operation at R th position so if we want substrings to be equal Dr must be 0. Therefore the alternating sum of Ci in range L to R must be zero for answer to be YES .

Can anyone pls explain.

Can someone check why my code is getting TLE. The time complexity is O(q*(r-l))

void solve() {
ll n, q;
cin >> n >> q;

string original_a, original_b;
cin >> original_a >> original_b;

for(int i = 0; i < q; ++i) {
ll l, r;
cin >> l >> r;
string a = original_a;
string b = original_b;

bool ans = true;

for(int i = l-1; i < r-1; ++i) {
ll steps = a[i] < b[i] ? b[i] - a[i] : 26 - abs(b[i] - a[i]);
a[i] = 'a' + ((a[i] - 'a') + steps) % 26;
a[i+1] = 'a' + ((a[i+1] - 'a') + steps) % 26;

if(a[i] != b[i]) {
ans = false;
break;
}
}

if(a[r-1] != b[r-1]) {
ans = false;
}

if(ans) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}

1 Like

Well we have answer each query in O(1) or O(logn) time but u are using (r-l) which will give tle

reverse the range and check again if any of them passes your result

Thanks, updated.

int c = (b[i-1]-a[i-1]+26)%26
How did you come up with this?

The time complexity of provided solution for each query is O(1) rather than O(R-L). The editorial also missed a part of prefix sum.

We can use…that’s not a problem

you have to construct the array of differences first and then run the query loop