PROBLEM LINK:
Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
We need to construct a binary string S of length N such that for string T which is the reverse of S, it needs to satisfy the condition S_i \neq T_i for all 1 \leq i \leq N. If it is not possible, we need to output -1.
EXPLANATION:
-
Since T is the reverse of S, we have S_i = T_{N-i+1}.
-
I claim that we cannot construct such string S if N is odd. This is because, for any string S, if we consider the index i = \frac{(N+1)}{2},
\hspace{0.79 cm} S_{\frac{(N+1)}{2}} = T_{N - \frac{(N+1)}{2} +1}
\implies S_{\frac{(N+1)}{2}} = T_{\frac{(N-1)}{2} +1}
\implies S_{\frac{(N+1)}{2}} = T_{\frac{(N+1)}{2}}
which is a contradiction to our problem statement. -
If N is even, we can construct our string S as the following: For all indices 1 \leq i \leq \frac{N}{2}, S_i = 0 and for all indices \frac{N}{2} \lt i \leq N , S_i =1. In this case S_i \neq S_{N+1-i} \implies S_i \neq S_{N+1-(N+1 -i)} \implies S_i \neq T_i for all 1 \leq i \leq N.
TIME COMPLEXITY:
O(N) for each testcase.
SOLUTION:
Editorialist's solution
#include <iostream>
using namespace std;
int main() {
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
if (n % 2 == 1) {
cout << -1 << endl;
}
else {
for (int i=0; i<n/2; i++) {
cout << 0;
}
for (int i=n/2; i<n; i++) {
cout << 1;
}
cout << endl;
}
}
return 0;
}
Setter's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while (t--){
int n;
cin>>n;
if (n%2 == 1)
cout<<-1<<endl;
else{
for (int i = 0;i<n/2;i++)cout<<0;
for (int i = n/2;i<n;i++)cout<<1;
cout<<endl;
}
}
return 0;
}
Tester's solution
def main():
s="01"
for _ in range(int(input())):
n=int(input())
if n%2:
print(-1)
else:
print(s*(n//2))
main()
Please comment below if you have any questions, alternate solutions, or suggestions. 
