S08E12 - Editorial

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: 11001110101110001
      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: 010010100010100001
      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;
}

Can anyone help me why I am getting WAs. Here is my code

plz make a video editorial

1 Like

@notsoloud , I have figured out a test case :
1
6 8
010011
01010010
The optimal answer according to me is 4, but some solutions giving a output of 5 is also getting passed.
Here is one example : Solution: 54539629 | CodeChef
Pardon me If I am wrong somewhere.
Thanks!

2 Likes

https://www.codechef.com/viewsolution/54537802
another solution giving 3 in your case which shouldn’t pass but it passed

can you find some case where my solution is failing as its giving wa and i cant find any case, I would be thankfull if you can help me out with this
link to my solution code

@mourya_satyam , I found one,

1
4 6
1101
100101

The op should be 3, but your solution gives 4

2 Likes

thankyou so much, Its great help got it ac there was just a small typo ruined my rank

Are you saying this can be solved in 3 steps instead of 4? If so, could you show the 3 steps?

can you please explain how you handled the case where size of S < size of T in setter solution ?
@notsoloud

yes sure,
First add 11 in the beginning of S, so cost till now is 2.
Now the string become
S :111101
T:100101
considering 0-based indexing, now we can peroform the operation 1 at index (1,2) which will cost 1 and now S: 100101 same as T.
So total cost 2+1 =3;
Hope it helps!!

1 Like

Yes. Thanks.

I have no idea my my code is not working, please help me out
https://www.codechef.com/viewsolution/57710804