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:
- Both S_1 and S_2 are palindromes.
- 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:
- 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.
- If X is 1, then we can only create one palindrome, therefore X cannot be 1. Similarly, Y cannot be 1.
- 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';
}
}
}