1557C - Moamen and XOR

Problem statement

Link : https://codeforces.com/contest/1557/problem/C
 

Gist

You are given numbers from \[0, $2^{k}$), where you can select any number with repetitions, to create an array of size $n$. Once you do so - you then & all the numbers to get A, and ^ all the numbers to get B.

Find the number of possible arrays such that $A >= B$
 

Solution

Let's look for a case where we are looking into only the bottom $i$ bits. So we have from \[0, $2^i$) to create an array of size $n$. Now, we can divide this range into two - \[0,$2^{i-1}$) and \[$2^{i-1}$,$2^i$). Let's call them groups A and B respectively.

If we select all the $n$ numbers from group B, then the highest bit will be the $(i-1)^{th}$ bit.

Now if $n$ is even, then ^ of this highest bit will be zero. But & of the highest bit will be one - which by default makes the & greater then ^ no matter what values of the lower bits is taken. Therefore in this case, we can select any numbers from group-B = $(2^{i-1})^{n}$

If $n$ is odd, then ^ and & both are zero, which then makes this equivalent to the case, when the highest bit is equal to zero - which is equal to getting the answer for group A. That is, for $i$ we are using the answer from $i-1$.

Now let's think about picking only *some* items from the group-B. If we select odd items, then & will be zero (as all higher bits are not 1 only *some* are), but ^ will be 1. So we can not do that.

So let's think selecting even items - then both & and ^ are zero.

If we select zero items from group B = ans(i-1)

If we select 2 items from group B = $^{n}C_2$ - to decide the positions of where to put 1s $\times$ ans(i-1) (because the lower bits will need to take the responsibility of satisfying the & >= ^ condition)

Again we select 4 items from group B = $^{n}C_4 \times \text{ans(i-1)}$
...
And this goes until we reach the highest even number under n (note that not n, as we already have calculated that)

We can take the ans(i-1) as common, and pre-compute $^{n}C_2 + ^{n}C_4 + ...$

And multiply this with ans(i-1) later.

Also we need to add the case when we deliberately are not selecting any number from group B, that is again just equal to ans(i-1)

Summing all this gives you ans(i), and you can create a dp, to calculate ans(k) which would be the answer.

My submission : https://codeforces.com/contest/1557/submission/306945910
 

Learnings

- Only deep thinking can solve these problems. Surface level thinking is just a waste of time for these problems.