 ANTIPAL - Editorial

Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Ajit Sharma Kasturi

CAKEWALK

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. I understand the method the editorial suggests (i.e., N must be an even number, then N/2 '0’s and N/2 '1’s or vice versa). I tried alternating 0’s and 1’s for even numbers and got a WA. Shouldn’t that work. For instance if N= 8, shouldn’t 01010101 or 10101010 wor?

1 Like

The above approach will always work. Check your code again. Your code is not passing the given pre test cases (not printing the string of required length).

In solution ans for inputting 8 ans is coming 00001111, whereas in my solution it’s coming 11110000 which is also correct I guess and satisfying the conditions. But it’s not accepted. Will you please have a look?

I don’t think these solutions are good, because they are always generating the same binary string. Let’s say n = 8, then the output of the editorial code is always 00001111.

What we can do is :
Any number, string, binary string is a palindrome only if half right of it is reverse of its half left.
Eg. 1011 1101 → 10111101 is a palindrome
1010 0101 → 10100101 is a palindrome
So, we can just make a random binary string of length n/2 for the left half and add a string of the length n/2 for the right half.
Choosing string for right half
We just have to make sure that the right half is not the reverse of the left half.
So, for the right half take the reverse of the left half and take its one’s complement.
Eg. 1011 — left half
1101 — reverse of the left half
0010 — one’s complement of 1101 (right half)
final string ----- 1011 0010
which is non-palindromic.

.

1 Like

I also tried this strategy and got WA. PLease asnwer why is it wrong ?

I think you forgot to add a new line character ("\n") after printing the binary string.

Yeah… even I have followed the same approach and got a WA. Can anyone explain why is it so?

Might be some implementation mistake, can’t tell without having a look over your code.

from sys import stdin