# PALINPAIN - Editorial

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

Cakewalk

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

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

1β€X, Yβ€10^3

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;

}