 Setter: munch_01
Testers: tabr

1216

None

# PROBLEM:

You are given two integers A and B.

Determine whether it is possible to construct two distinct binary palindromes S and T where both S and T have exactly A 0's and B 1's.

# EXPLANATION:

If both A and B are even then the answer is “Yes”, because you can construct a string with \frac{A}{2} 0's, followed by B 1's, followed by \frac{A}{2} 0's.

Eg. if A = 6, B = 4, then you can construct 0001111000

You can construct the other string with \frac{B}{2} 1's, followed by A 0's, followed by \frac{B}{2} 1's.

Now, if both A and B are odd, then no palindrome exists, so the answer is “No”. This fact is easy to verify.

If exactly one of them is odd and also >1, then the answer is “Yes” again. The construction for this case is similar to the first case. If you assume that A is odd and B is even. You can construct the first string with \frac{A-1}{2} 0's, followed by \frac{B}{2} 1's, followed by a 0, followed by \frac{B}{2} 1's, followed by \frac{A-1}{2} 0's. The second string is \frac{B}{2} 1's, followed by A 0's, followed by \frac{B}{2} 1's.

If either A or B is 1, then the answer is “No”.

# TIME COMPLEXITY:

Time complexity is O(1).

# SOLUTION:

Editorialist's Solution
#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
if(a%2 && b%2){
cout<<"No\n";
}
else if(min(a, b) == 1){
cout<<"No\n";
}
else{
cout<<"Yes\n";
}
}
return 0;
}


1 Like

Hello…
Why do we have to check for 1 in a and b?
Isn’t 0001000 a palindrome?
Thanks

We have to construct two DIFFERENT palindrome.
If either A or B is 1 then we cannot construct two different palindromes.

Ohh yeah…sorry I didn’t realise that… thanks😁

(post deleted by author)

000111 and 111000 are no palindromes. A palindrome is a word that must be the same whether you read it from the left or from the right. The name “Hannah” is a palindrome, for example.