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] = 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";
}
}
}
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.
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,
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
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 .
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.