bro that is obvious coz in one operation we are changing a[i] and a[i+1] so how can we perform the operation on the last index, you cannot change a[n] alone there has to a[n+1] to perform the operation
bro can you tell me the reason for taking mod 26 at the end when calculating prefix sum from L to R
why this → (E[r]-E[l-1])%26. I am getting WA if I am not doing this. and what is the need to do this anyways, this is never going to overflow then why mod?
why are we taking mod at last when calculating sum from L to R
(E[r]-E[l-1])%26 why mod 26?
We just need to check whether this is 0 or not and this is never going to overflow then why?
Hi! I have tried to solve this problem by checking if all the characters , b[i] - a[i] gives same difference. Can anyone please help me finding why I am getting Wrong Answer on submission
#include<bits/stdc++.h>
#define int long long int
using namespace std;
void output();
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin>>t;
while(t--){
output();
}
return 0;
}
void output(){
int n,q;
cin>>n>>q;
string a,b;
cin>>a>>b;
int i,j;
while(q--){
cin>>i>>j;// 4 5
int common_diff = (b[i-1] - a[i-1] + 26)%26;
// if(common_diff<0){
// common_diff += 26;
// }
bool ans = true;
for(int k=i;k<=j-1;k++){ // 4,4
// abcdz
// nbhea
int variable_diff = (b[k] - a[k] + 26)%26;
// if(variable_diff < 0){
// variable_diff += 26;// -25 + 26 = 1
// }
if(common_diff != variable_diff){
ans = false;
break;
}
}
if(ans){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
cout<<"\n";
}
I don’t assume whatever comes to my mind. It was a rated contest. The problem statement has to be clear enough. Moreover, I am not talking about operations on the whole string. It is then obvious that you cannot pick i = n - 1. It was not mentioned anywhere that we cannot pick i = R.
Editorials are roadmaps to the algorithm(s), which, when coded carefully leads to an AC. The algorithm which author has tried to convey through this editorial fits well withing the time constraints and does not give a TLE.
Possibly, you didn’t get the whole idea or the implementation. For the later one you can refer to the code provided. We will be able to help you with the understanding of the editorial if you tell us what you have understood so far (just try to elaborate on why you think this will take too long).
We can choose i\in [L, R - 1]. Choice (% 26) is fixed for A[L] and once we have chosen that, $A[L + 1] changes. As there is no point changing A[L] again we can apply the same logic now on updated A[L + 1]. This goes on until have we chosen our operations for all except A[R]. But due to constraints we cannot choose i to be R. Hence whatever changes we had done in A[R - 1] better make A[R] = B[R]. The mentioned alternation sum counts just that change.
If you think your solution is correct, you are claiming that if and only if the difference between all the indices in given range is same, will the satisfying operations exist.
Let us suppose strings were A[L, R] = "abc" and B[L, R] = "def". I claim that it satisfies your condition. Try to work out set of valid operations for this. I claim it cannot be done. So this proves that when you say “Yes” answer could be a “No”.
Now, consider A[L, R] = "abf" and B[L, R] = "def". Here if we choose i = L and increase by 3, A'[L, R] = "def". Hence, answer should be a “Yes”, but your code will print a “No”.
Also complexity of you code is bad. But first try to come up with a correct solution and then we can worry about complexity.
Hi,
Can anybody plz help me understand how to calculate the prefix sum in this particular case?
As explained in the editorial, D[i] = C[i] - D[i-1], i.e, The value at D[R] = C[R] - C[R-1] + C[R-2] - … and so on. Since this sequence in C is an alternating sum sequence, (i.e. C1, C2 - C1, C3 - C2 + C1,… and so on ), can we directly store these values in an array and compute C[R] - C[L-1] ??
You are not restoring the string a after the queries where you change the string. Problem states that queries are independent, hence in each query we must work on the same strings.
