BINXOR - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Akash Tike
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
EASY
PREREQUISITES:
Binary operations, modular arithmetics
PROBLEM:
You’re given two binary strings A and B of length N. Let A' and B' be strings A and B shuffled in some specific way. Calculate the number of distinct possible values of their xor A' \oplus B'.
QUICK EXPLANATION:
consider minimum and maximum number of ones in A' \oplus B' you can obtain. Any number of ones between them with the same parity can be achieved.
EXPLANATION:
First of all, since the order of ones and zeros in the input doesn’t matter, we may assume that the answer is determined by the number of ones in given strings. Let it be N_A and N_B for strings A and B correspondingly. It’s quite easy to see that minimum possible number of ones in A' \oplus B' is L=|N_A-N_B| since we may sort both A and B.

And the maximum number of ones is R=|N_A+N_B-2 \cdot \max(0, N_A + N_B - N)| since we may put N_A ones in the beginning of A' and N_B ones in the end of B'. If N_A+N_B > N then their intersection is of the size (N_A+N_B-N) so we should double subtract it to get the symmetric difference of the sets of positions of ones in A' and B'.

Gradually shifting starting position of the block of ones in B' we may obtain any intermediary (with same parity) number of ones in A' \oplus B' and applying same permutation to both A' and B' we may rearrange them in any way. Note that the parity of ones in A' \oplus B' is invariant and determined by the parity of the number of ones in A' and B' only, thus it constitutes all possible answers. That being said, we have to sum up \binom{N}{k} with k going from L to R with the step of 2:

void solve() {
	int N;
	cin >> N;
	string A, B;
	cin >> A >> B;
	int Na = count(begin(A), end(A), '1');
	int Nb = count(begin(B), end(B), '1');
	int ans = 0;
	int L = abs(Na - Nb);
	int R = Na + Nb - 2 * max(0, Na + Nb - N);
	for(int k = L; k <= R; k += 2) {
		ans = (ans + nCr(N, k)) % mod;
	}
	cout << ans << endl;
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.
Editorialist’s solution can be found here.

4 Likes

Why we are incrementing the counter by 2?

Let us take the example of possible XORs of two strings:
1110
0101
Here we see that maximum possible number of 1s is 3 and min is 1. But if we try to find a permutation with 2 1s, it is not possible. Therefore parity should remain same

@neel19 You can look it in this way.
Suppose A = 00001111 and B= 00001100
Here the result will be 3 i.e (11)
now if you want a different result having more than 2 set bit’s in the result you need to exchange 2 positions of any number so in that process you are changing 2 bits hence the next result will contain 4 set bits. Hence it is incremented by 2

1 Like

Because if you unmatch one pair you end up generating two unmatched pairs

How to calculate (1/N!)%mod ?
Please suggest the topics of modular arithmetic used in cp.

If MOD is a Prime Number, use Fermet Little Algorithm, Google it!

So (L-R) will be always be even?

Why do we need to find the modulo multiplicative inverse here?

can anyone here explain me how to find all the combinations of a given string eg: 11001 it would be better if anyone build up the context in the way to earn 10 points then 30 then 60 so that the learning will be smooth …

1 Like