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.

1528B - Kavi on pairing duty

Problem statement

Link : https://codeforces.com/problemset/problem/1528/B
 

Gist

There are $2 \times n$ points on the X-axis. You join every point to *some* other point. So it can have different permutations. A permutation is "good" if for all the connections, at least one these hold:
1. Connection A is within connection B - so let's say we have 1,2,3 and 4. And 1 and 4 are connected, and 2 and 3 are connected. So 2 and 3 is *within* 1 and 4. Therefore this works.
2. Connection A is of the same length as connection B. Again let's say we have 1,2,3 and 4. 1 and 2 are connected, and 3 and 4 are connected. Since 1 and 2's connection is of length 1 and 3 and 4's connection is also of length 1 this is a good permutation.

Given the input $n$ we need to output the number of good permutations.

Solution

Thinking

Let's think about the case of over-arches. That is, let's say you have some $n$, and you have a connection from 1 to 2n. Then you have 2n-2 points inside this connection / arch. For each of these connection & this arch, the first condition holds, as each connection is within this arch. Therefore we can just add the answer of $n-1$ input to get that value.

Let's think about the cases when there are no arches.

Can we have small arches which have the other arches within them, but are separate from other small arches? Like for example, let's say $n = 10$. Then you can divide it into 5 groups of 4 points. So can we re-use the answer for 4 here?

The issue here is that the arch of group1 and the inner connection of group2 don't satisfy any condition. Neither they are within each other - as the group 2 connection is not within group 1's arch. Nor do they have the same length, as group 2 connection is smaller than group 1's arch.

One other condition where this can work is you have a group of connections which are of the same length, which are archs for other connections which are smaller but again of the same length. So again the same rule applies like the 1 super arch. Everything inside actually satisfies the first property with these archs, so we can use the previous answers here. So instead of just adding $ans(n-1)$ we add everything from $ans(1)$ ... $ans(n-1)$ here.

Now that, that is out of the picture, besides the 1 super arch, can we have cases when connection lengths are different? If there are two connections with different lengths then one of them needs to be inside the other connection. Since we can't have groups of such archs, having smaller connections within them, then this would mean that if we have connections with different length, we need to have a composition of arches within each other. 1-10, 2-9, 3-8, 4-7, 5-6 - but this is already covered as the first case. 1-10 + $ans(8)$ as the answer of 8 will already contain this case.

Therefore from this we understand that the other case is the only one when all of the connection lengths are the same.



How do we calculate them? So basically you have $2 \times n$ points, and you want to divide them into *some* equal points. Seems like the number of factors would do? Yep.

So for $n$ we find the number of factors - all of them, and add those to $\sum_{i=1}^{n-1} ans(i)$ - and that pretty much is the answer here. This summation can be saved in a var.
 

Implementation

My implementation took 999ms when the time limit was 1000ms. Take this with a grain of salt. I think there definitely should be a better solution.

$dp[n] = (\sum_{i=1}^{n-1}dp[i]) + factors(n)$

Here finding $factors(n)$ efficiently is the main problem. I did it by keeping a vector of `unordered_map`s which kept the number of prime factors. So for example, for $12 = 2^2 \times 3^1$ we save in the map 12 : {{2,2}, {3,1}}. Now if you want to find the number of factors, you just do $(powerOf2+1) \times (powerOf3 + 1)$ = $(2 + 1) * (1 + 1)$  = 6.

12 has 1, 2, 3, 4, 6, 12 as the factors. Yes we are counting the number itself as well in this case.

You get a list of primes, using sieve of eratosthenes, and then find the first prime that divides $n$. Once you get that, you re-use $n / prime$ to query the `unoredered_map` to get it's factors, and then add 1 to the $prime$ you found. Then you use the current map to get factors, and save the map to the `unoredered_map` for $n$.

Here is the submission : https://codeforces.com/contest/1528/submission/304791168




## Learnings



## Timelog