THETRADE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Simple

PREREQUISITES:

Greedy

PROBLEM:

You are given two strings A and B of the same length N. For all i such that 1\leq i\leq \frac{N}{2}, the following operations can be performed any number of times:

  • Swap A_i with B_i
  • Swap A_i with A_{N-i+1}

You have to tell the minimum number of operations needed to make the strings equal. Or determine that it’s impossible.

QUICK EXPLANATION:

The section below explains better.

EXPLANATION:

For all i such that 1\leq i\leq \frac{N}{2}, we’ll try to make A_i == B_i.
Let’s form cases for all i such that 1\leq i\leq \frac{N}{2}:

  • If A_i == B_i, do nothing and move to the next index.
  • Else if A_{N-i+1} == B_i, we can swap A_i and A_{N-i+1}. So now, A_i and B_i will be equal.
  • Else if A_{N-i+1} == A_i, we can perform 2 swaps. First, swap A_i and B_i. Then swap A_i and A_{N-i+1}.

Now, we have managed to make A[1,N/2] equal to B[1,N/2]. All we need to check now is whether the final strings are equal.

Refer to the solutions below for implementation detials.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()

using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input4.txt","r",stdin);
    // freopen("output4.txt","w",stdout);
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n,i,ans=0,f=1;
        cin>>n;
        string a,b;
        cin>>a>>b;
        if((n & 1) && a[n/2] != b[n/2])
        {
            cout<<"-1\n";
            continue;
        }
        for(i=0;i<n/2;i++)
        {
            if(a[i] == b[i])
                continue;
            if(a[n-i-1] == b[i])
            {
                swap(a[n-i-1],a[i]);
                ans++;
            }
            else if(a[i] == a[n-i-1])
            {
                swap(a[i],b[i]);
                swap(a[i],a[n-i-1]);
                ans+=2;
            }
            else
            {
                f=0;
                break;
            }
        }
        if(!f || a != b)
            cout<<"-1\n";
        else cout<<ans<<"\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   int t;
   cin>>t;
 
   assert(t<=10);assert(t>=1);
 
   while(t--)
   {
      int n;
      cin>>n;
      assert(n<=100000);assert(n>=1);
 
      string A,B;
      cin>>A>>B;
      assert(A.length()==n);
      assert(B.length()==n);
      
 
      int ans=0,ok=0;
 
      for(int i=0;i<=n/2;i++)
      {
         assert(A[i]>='a');assert(A[i]<='z');
         assert(B[i]>='a');assert(B[i]<='z');
         
         if(A[i]!=B[i])
         {
            if(A[n-1-i]==B[i]){
               ans++;
               swap(A[n-1-i],A[i]);
            }
            else if(A[n-1-i]==A[i]){
               ans+=2;
               swap(A[n-1-i],B[i]);
            }
            else ok=1;
         }
      }
      if(ok==1||A!=B)
         cout<<-1;
      else cout<<ans;
      cout<<'\n';
 
   }
 
   return 0;
}

Feel free to write your approach in the comments :slight_smile:

1 Like