PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Kanhaiya Mohan
Tester: Nishant Shah, Divyansh Tyagi
Editorialist: Akshit Dhoundiyal
DIFFICULTY
Easy
PREREQUISITES
String manipulation
PROBLEM
Given 2 strings S and T. You need to calculate the minimum number of operations needed to convert string S to string T using the operations:
- flip the value of any 2 consecutive characters.
- add any character (0 / 1) to either end of the string.
EXPLANATION
Observation 1:
If the size of string S is greater than that of string T, then it is impossible to convert it.
Proof
We have no operation that is capable of reducing the size of our string.
First, we’ll try to make the size of both the strings equal. For this we will perform M - N operations of type 2. For now we don’t care about what values we’re adding or where.
Observation 2
We can convert string S to string T, only if the total number of inversions is even.
Proof
Say there is an index ‘i’ where we have an inversion. To change the value at that position we have to use the operation of type 1. As a result, the value at index ‘i + 1’ is also inverted. Now, if the characters at index $‘i + 1’ $were initially equal, we have a new inversion at that position. So, we apply the type 1 operation again at index ‘i + 1’. However the result would be the same. This will keep on happening until we encounter another inversion.
Let’s say that the next inversion is at index j. When we apply the type 1 operation at index$ ‘j - 1’$, characters of both$ ‘j -1’$ and ‘j’ become equal to their corresponding counterparts.
The same thing will happen at every pair of inversions.
In case we can’t find another index with an inversion to make a pair i.e. the number of inversions is odd, then there will be at least one index with an inversion left i.e. we won’t be able to convert our string entirely.
Now to calculate our answer, we assume a substring of string T of size N (size of string s) to come from the original string S (let’s refer to it as main part) while the other characters(if any) to be added as a result of type 2 operation (let’s refer to them as extra characters). Initially we consider the extra characters of both the strings to be equal. Then we count the number of inversions in the main part. Depending upon the parity of the inversions, we follow 2 separate paths to get the answer:
If the number of inversions is odd
Here we will have to add an additional inversion to get an answer(Observation 2). We can get that extra inversion from the extra characters.
If there are no extra characters then we will return -1.
Otherwise, we invert the closest extra character to the main part at either side. We will take the one which will give us an optimal solution.
If the number of inversions is even
We calculate the number of moves we need to perform to nullify each of the inversions.
Now, there exists a possibility that adding inversions to both sides of the main part would reduce the number of operations required.
For instance,
Normal solution:
Let S = 110011 (after adding extra elements(underlined)) and T = 100001.
S: 110011 → 101011 → 10001
Total moves = 2 (type 1) + 3 (type 2)
= 5
Adding inversions to both sides of main part:
Let S = 010010 (after adding extra elements(underlined)) and T = 100001.
S: 010010 → 100010 → 100001
Total moves = 2 (type 1) + 2 (type 2) = 4
It is not always true. You can check it by taking the case S = 1000110001 and T = 010001100010
So we will take the case which will give us an optimal answer.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007
int n, m;
string s, t;
int helper(list<int> &idx){
int steps =0;
auto itr = idx.begin();
while(itr!=idx.end()){
int c1 = *itr;
++itr;
int c2 = *itr;
++itr;
steps += c2 - c1;
}
return steps;
}
int solve(){
cin>>n>>m;
cin>>s>>t;
if(n>m) return -1;
if(n == m){
int mismatch = 0;
list<int> idx;
for(int i =0 ;i < n; i++){
if(s[i]!=t[i]){
mismatch+=1;
idx.push_back(i);
}
}
if(mismatch%2) return -1;
return helper(idx);
}
int steps = INT_MAX;
for(int i =0 ; i < m ; i++){
if((i+(n)-1) >= m) break;
int mismatch = 0;
list<int> idx;
for(int j =0 ;j < n; j++){
if(s[j]!=t[i+j]){
mismatch+=1;
idx.push_back(i+j);
}
}
if(mismatch%2 == 1){
if(i!=0){
idx.push_front(i-1);
steps = min(steps,helper(idx));
idx.pop_front();
}
if((i+(n-1))!=(m-1)){
idx.push_back(i+n);
steps = min(steps,helper(idx));
}
}else{
steps = min(steps,helper(idx));
if(i!=0 && (i+(n-1))!=(m-1)){
idx.push_front(i-1);
idx.push_back(i+n);
steps = min(steps,helper(idx));
}
}
}
return steps + m - n;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
sync;
int t = 1;
cin>>t;
while(t--){
cout<<solve();
cout<<"\n";
}
return 0;
}