TWODIFFPALIN - Editorial

PROBLEM LINK:

Contest
Practice

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;
}

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😁

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.