SOPC008 Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Medium

PREREQUISITES:

Constructive Algorithms, strings.

PROBLEM:

Given two binary strings, make both of them palindromes or report that it is not possible.

EXPLANATION:

First, since both strings are of even length, it is not possible to make both of them palindromic if frequency of each character is odd.

Now, consider the case when both occur an even number of times. This time, the answer definitely exists.

Consider the following process: let us consider all characters in String 1 from index 1 to n/2: and if s_{1,i} \neq s_{1,n+1-i}, we find a character such that s_{1,i}=s_{1,j} and i<j<n+1-i. If such a character exists, we do operation 1 on indices j and n+1-i. If such a character doesn’t exist, we search for it throughout string 2 and find s{2,j} such that s_{1,i}=s_{2,j} and perform operation 2 on indices n+1-i and j.

Convince yourself that string 1 is now a palindrome.

Now, we start string 2 from index 1 to n/2-1 (convince yourself why we don’t do this till position n/2): if s_{2,i} \neq s_{2,n+1-i}, we find a character such that s_{2,i}=s_{2,j} and i<j<n+1-i. This time, the character exists definitely since the answer has to exist. Hence do operation 3 on j and n+1-i.

We are doing at most 1 operation in each iteration and we are doing n-1 iterations, hence we are doing at most n-1 operations.

This is one of multiple similar solutions. All correct answers shall be given AC verdict.

SOLUTION:

Setter's Solution 
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a>b)?a:b)

using namespace std;

void solve()
{
    ll n;
    cin>>n;
    string s1,s2;
    cin>>s1>>s2;
    ll co=0;
    for(int i=0;i<n;i++)
    {
        if(s1[i]=='a')
            co++;
        if(s2[i]=='a')
            co++;
    }
    if(co%2==1)
    {
        cout<<-1<<endl;
        return;
    }
    vector<tuple<ll,ll,ll>>> ans;
    for(ll i=0;i<n/2;i++)
        if(s1[i]!=s1[n-1-i])
        {
            bool flag=false;
            for(int j=i+1;j<n-i-1;j++)
            {
                if(s1[j]==s1[i])
                {
                    flag=true;
                    char temp=s1[j];
                    s1[j]=s1[n-1-i];
                    s1[n-1-i]=temp;
                    ans.push_back(make_tuple(1,i,j));
                    break;
                }
            }
            if(flag)
                continue;
            for(int j=0;j<n;j++)
                if(s2[j]==s1[i])
                {
                    char temp=s2[j];
                    s2[j]=s1[n-1-i];
                    s1[n-1-i]=temp;
                    ans.push_back(make_tuple(2,i,j));
                    break;
                }
        }
    for(ll i=0;i<n/2;i++)
        if(s2[i]!=s2[n-1-i])
            for(int j=i+1;j<n-i-1;j++)
                if(s2[j]==s2[i])
                {
                    char temp=s2[j];
                    s2[j]=s2[n-1-i];
                    s2[n-1-i]=temp;
                    ans.push_back(make_tuple(3,i,j));
                    break;
                }
    cout<<ans.size()<<endl;
    for(ll i=0;i<ans.size();i++)
        cout<<get<0>(ans[i])<<" "<<get<1>(ans[i])<<" "<<get<2>(ans[i])<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}
2

Although somewhat standard question, still I had fun writing the code for it!

1 Like
3

I think that this can be done in N/2 operations. (Don’t know if I’m missing something)
Consider traversing both strings at the same time till the middle. At each position, consider 2 sets of characters at the position and mirror position, for both strings. Then the possibilities are :

  1. Both characters in both strings are equal \implies we move to next index
  2. Both characters in both strings are unequal \implies we can do an operation of type 2 to make both sets equal.
  3. Only one character differs from rest all \implies we can search for an equal character in both strings and do the required operation.
    Since we are doing atmost one operation per position, we have atmost N/2 operations to make.
    Is this right?
4

What if we have to convert them in min no of steps…
Any similar problem pls…

5

Why we start from n/2-1 instead of n/2 in string 2.

6

The setter’s solution you provided assumes 0-based indexing, whereas the problem statement has 1-based indexing.