PROBLEM LINK:
Setter: munch_01
Testers: tabr
Editorialist: aryanag_adm
DIFFICULTY:
1216
PREREQUISITES:
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;
}