PALINPAIN - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S.Manuj Nanthan
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

Cakewalk

PREREQUISITES:

String

PROBLEM:

You are given two integers X and Y. You need to construct two different strings S_1 and S_2 consisting of only the characters \texttt{a} and \texttt{b}, such that the following conditions are satisfied:

  1. Both S_1 and S_2 are palindromes.
  2. Both S_1 and S_2 should contain exactly X occurrences of \texttt{a} and Y occurrences of \texttt{b}.

If there are multiple possible answers, you may print any of them. If it is not possible to construct two distinct strings satisfying the conditions, print -1 instead.

EXPLANATION:

Notice the following:

  1. If X is odd, we need to put \texttt{a} right in the middle of S_1 and S_2. Similarly, if Y is odd, we need to put \texttt{a} right in the middle of S_1 and S_2. Therefore, X and Y cannot be odd at the same time.
  2. If X is 1, then we can only create one palindrome, therefore X cannot be 1. Similarly, Y cannot be 1.
  3. Otherwise, after knowing what the middle character is, build the first half of S_1 by using \frac{X}{2} \texttt{a} characters first, then \frac{X}{2} \texttt{b} characters later; similarly, build the first half of S_2 by using \frac{Y}{2} \texttt{b} characters first, then \frac{X}{2} \texttt{a} characters later.

TIME COMPLEXITY:

Time complexity is O(X + Y) for each test case.

SOLUTION:

Setter's Solution 
for _ in range(int(input())):
    x,y=map(int,input().split())
    if(x==1 or y==1 or (x%2 and y%2)):
        print(-1)
        continue
    n=x+y
    first=['']*n
    if(x%2):
        first[n//2]='a'
        x-=1
    if(y%2):
        first[n//2]='b'
        y-=1
    for i in range((n - (n%2))//2):
        if(x):
            x-=2
            first[i]='a'
            first[-1-i]='a'
        else:
            first[i]='b'
            first[-i-1]='b'
    print(''.join(first))
    for i in range(n):
        if(first[i]!=first[i+1]):
            first=first[:i+2][::-1]+first[i+2:]
            first= first[:n-(i+2)]+ first[n-(i+2):][::-1]
            break
    print(''.join(first))
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=1e5+1;
int n;
int a[N],b[N];
void solve(){
	int x,y;
	cin >> x >> y;
	if(x==1 || y==1) cout << "-1\n";
	else if(x%2==0){
		for(int i=1; i<=x/2 ;i++) cout << 'a';
		for(int i=1; i<=y ;i++) cout << 'b';
		for(int i=1; i<=x/2 ;i++) cout << 'a';
		cout << "\nb";
		for(int i=1; i<=x/2 ;i++) cout << 'a';
		for(int i=1; i<=y-2 ;i++) cout << 'b';
		for(int i=1; i<=x/2 ;i++) cout << 'a';
		cout << "b\n";
	}
	else if(y%2==0){
		for(int i=1; i<=y/2 ;i++) cout << 'b';
		for(int i=1; i<=x ;i++) cout << 'a';
		for(int i=1; i<=y/2 ;i++) cout << 'b';
		cout << "\na";
		for(int i=1; i<=y/2 ;i++) cout << 'b';
		for(int i=1; i<=x-2 ;i++) cout << 'a';
		for(int i=1; i<=y/2 ;i++) cout << 'b';
		cout << "a\n";
		
	}
	else cout << "-1\n";
}
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;while(t--) solve();
}
Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int x, y; cin >> x >> y;
        if (x == 1 || y == 1 || (x % 2 == 1 && y % 2 == 1)) {
            cout << "-1\n";
        } else {
            char mid = (x % 2 == 1 ? 'a' : y % 2 == 1 ? 'b' : '#');
            // mid != '#' indicates whether to put middle character or not
            string s1 = string(x / 2, 'a') + string(y / 2, 'b') + string(mid != '#', mid) + string(y / 2, 'b') + string(x / 2, 'a');
            string s2 = string(y / 2, 'b') + string(x / 2, 'a') + string(mid != '#', mid) + string(x / 2, 'a') + string(y / 2, 'b');
            cout << s1 << '\n' << s2 << '\n';
        }
    }
}
4 Likes
4

For the case of
2 0
solution prints
aa
aa
but these two strings aren’t different

5

1≤X, Y≤10^3

6

Can someone help me here.

#include
using namespace std;

int main()
{
long long int T, a, b;
string s1, s2;
cin>>T;
while(T–){
cin>>a>>b;
if(a == 1 || b == 1 || a == 0 || b == 0){
cout<<-1<<endl;
}
else if(a%2 == 0 && b%2 != 0){
for(int i = 0; i < a+b; i++){
if(i < b/2){
cout<<‘b’;
}
else if(i < (a/2+b/2)){
cout<<‘a’;
}
else if(i == (a/2 + b/2)){
cout<<‘b’;
}
else if(i < (a + b/2)){
cout<<‘a’;
}
else{
cout<<‘b’;
}

        }
        cout<<endl;
        
        for(int i = 0; i < a+b; i++){
            if(i < a/2){
                cout<<'a';
            }
            else if(i <= (a/2+b)){
                cout<<'b';
            }
            else{
                cout<<'a';
            }
            
        }
        cout<<endl;
    }
    else if(a%2 != 0 && b%2==0){
        for(int i = 0; i < a+b; i++){
            if(i < a/2){
                cout<<'a';
            }
            else if(i < (a/2+b/2)){
                cout<<'b';
            }
            else if(i == (a/2 + b/2)){
                cout<<'a';
            }
            else if(i <= (b + a/2)){
                cout<<'b';
            }
            else{
                cout<<'a';
            }
            
        }
        cout<<endl;
        for(int i = 0; i < a+b; i++){
            if(i < b/2){
                cout<<'b';
            }
            else if(i < (b/2+a)){
                cout<<'a';
            }
            else{
                cout<<'b';
            }
            
        }
        cout<<endl;
    }
    else if(a%2 == 0 && b%2 == 0){
        for(int i = 0; i < a+b; i++){
            if(i < a/2){
                cout<<'a';
            }else if(i < (b + a/2)){
                cout<<'b';
            }
            else{
                cout<<'a';
            }
        }
        cout<<endl;
        for(int i = 0; i < a+b; i++){
            if(i < b/2){
                cout<<'b';
            }else if(i < (a + b/2)){
                cout<<'a';
            }
            else{
                cout<<'b';
            }
        }
        cout<<endl;
    }
    else{
        cout<<-1<<endl;
    }
}

return 0;

}