Editorial for Funny Bits

Editorial

Let us go with the example where $k = 4$, $a = 7$, and $n = 2$.

In other words, summing all positive integers that can be represented with at most $k = 4$ bits with exactly $n = 2$ bits that equal to $1$, average it then round it down will get $a = 7$.

Question 1: How many numbers are there where $k = 4$ and $n = 2$?**

We notice that there will be a total of $2^{k} = 2^k = 16$ non-negative integers that can be represented with at most $k = 4$ bits.

Each bit can be either set or unset (either $1$ or $0$). There are $k = 4$ digits for each number, and we are choosing exactly $n = 2$ of those bits to be set. This is a combination problem, and the number of ways to choose $n$ bits out of $k$ is given by the combination formula $nCr(k, n) = nCr(4, 2) = 6$.

Question 2: What is the sum of all numbers where $k = 4$ and $n = 2$?**

A brute-force solution that generates all required numbers then summing it could work for smaller numbers of $n$ and $k$, but anything above $n = 15$ would likely kill your computer.

Instead, we make a few observations:

• There are $nCr(k, n) = 6$ numbers in total.
• Out of every single digit in all numbers, only $n / k = 50$ of all digits will be set.
• For all $nCr(k, n) = 6$ numbers, each column of digits will have exactly the same number of set bits.

Knowing the above, we can deduce that there will be a total of $nCr(k, n) * \left(n / k\right)$ bits set for every digit position. In other words, the sum of all numbers can be calculated as $\sum_{i = 0}^{k - 1}{\left( 2^{i}\times\frac{n}{k}\times\text{nCr}\left(k, n\right) \right)} = 45$.

Question 3: How do we find the rounded-down average?

We have the sum and count from above. Dividing the sum by the count with a floor function attached to it would $\text{floor}\left(\frac{\sum_{i = 0}^{k - 1}{\left( 2^{i}\times\frac{n}{k}\times\text{nCr}\left(k, n\right) \right)}}{\text{nCr}\left(k, n\right)}\right) = 7$

This formula can be further simplified to $\frac{n}{k}\times{\left(2^{k}-1\right)}=7$.

Question 4: How do we find $n$ from $k$ and $a$?

Now that we have a formula that calculatees $a$ from $n$ and $k$, ignoring the floor function, the formula can be rearranged as $n = \frac{a * k}{2^{k} - 1}$. Adding a round function to this would pass all test cases.

Final Implementation

k, a = map(int, input().split())
print(round(a * k / ((1 << k) - 1)))