Game Bundles
Contest: Codeforces Round 889 (Div. 1)
Difficulty rating: 3000
Tags: brute force, constructive algorithms, dp, greedy, math

Rishi is developing games in the 2D metaverse and wants to offer game bundles to his customers. Each game has an associated enjoyment value. A game bundle consists of a subset of games whose total enjoyment value adds up to $$$60$$$.

Your task is to choose $$$k$$$ games, where $$$1 \leq k \leq 60$$$, along with their respective enjoyment values $$$a_1, a_2, \dots, a_k$$$, in such a way that exactly $$$m$$$ distinct game bundles can be formed.

Input format:
The input is a single integer $$$m$$$ ($$$1 \le m \le 10^{10}$$$) — the desired number of game bundles.

Output format:
The first line should contain an integer $$$k$$$ ($$$1 \le k \le 60$$$) — the number of games.

The second line should contain $$$k$$$ integers, $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_1, a_2, \dots, a_k \le 60$$$) — the enjoyment values of the $$$k$$$ games.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first sample, any subset of size $$$3$$$ is a game bundle. There are $$$4$$$ such subsets.

Example input:
4

Example output:
4
20 20 20 20

Example input:
722

Example output:
15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Editorial:
We describe a randomized solution that solves the problem for $$$m$$$ up to $$$10^{11}$$$ (and, with some additional care, may be able to solve also $$$m$$$ up to $$$10^{12}$$$). We decided to give the problem with the smaller constraint $$$m\le 10^{10}$$$ to make the problem more accessible and because there may be some rare cases below $$$10^{11}$$$ for which our solution is too slow (even though we could not find any). We don't know any provably correct solution, if you have one we would be curious to see it.
Main idea: Choose suitably the values $$$a_1, a_2, \dots, a_h$$$ that belong to $$$[1,29]$$$ and then find $$$a_{h+1}, a_{h+2},\dots,a_k$$$ in $$$[31,60]$$$ by solving a backpack-like problem.
Let us describe more precisely the main idea. Assume that $$$a_1, a_2, \dots, a_h\le 30$$$ are fixed and they satisfy $$$a_1+a_2+\cdots+a_h<60$$$. For any $$$s=0,1,2,\dots,29$$$, let $$$f(s)$$$ be the number of subsets $$$I\subseteq\{1,2,\dots,h\}$$$ so that $$$\sum_{i\in I}a_i=s$$$. If we can find some values $$$0\le s_1,s_2,\dots,s_{k-h}\le 29$$$ so that $$$f(s_1)+f(s_2)+\cdots+f(s_{k-h})=s$$$, then by setting $$$a_{h+i} = 60-s_i$$$ for $$$i=1,2,\dots, k-h$$$ we have found a valid solution to the problem.
There are two main difficulties:
• How can we find $$$s_1, s_2,\dots, s_{k-h}$$$?
• How should we choose $$$a_1, a_2,\dots, a_h$$$?
Since it is important to get a good intuitive understanding of the computational complexity of the algorithm, let us say now that we will choose $$$h\le 44$$$ and (accordingly) $$$k-h=16$$$. These values are flexible (the solution would still work with $$$h\le 45$$$ and $$$k-h=45$$$ for example). We will say something more about the choice of these values when we will describe how $$$a_1,a_2,\dots, a_h$$$ shall be chosen.
The backpack problem to find $$$s_1, s_2,\dots, s_{k-h}$$$.
The naive way to find $$$s_1,\dots, s_{k-h}$$$ would be to try all of them. There are $$$\binom{k-h + 29}{29}$$$ possible ways (up to order, which does not matter). Since $$$k-h=16$$$ this number is $$$\approx 2\cdot 10^{11}$$$ which is too much to fit in the time limit.
To speed up the process, we will do as follows. Partition randomly $$$A\cup B=\{0,1,\dots, 29\}$$$ into two sets of size $$$15$$$. We iterate over all possible $$$s_1, s_2, \dots, s_{(k-h)/2}\in A$$$ and over all possible $$$s_{(k-h)/2+1},\dots, s_{k-h}\in B$$$ and check whether the sum of one choice from the first group and one choice from the second group yields the result. This is a standard optimization for the subset sum problem. What is its complexity? It can be implemented in linear time in the size of the two groups we have to iterate over, which have size $$$\binom{(k-h)/2+15}{15}\approx 5\cdot 10^5$$$. Notice that in this faster way we will not visit all the $$$\binom{k-h+29}{29}$$$ possible choices $$$s_1,s_2,\dots, s_{k-h}$$$ because we are assuming that exactly half of them belong to $$$A$$$ and exactly half of them belong to $$$B$$$. This is not a big deal because with sufficiently high probability we will find a solution in any case.
The choice of $$$a_1, a_2,\dots, a_{h}$$$.
It remains to decide how we should select $$$a_1, a_2, \dots, a_{h}$$$. The following choice works:
• Approximately the first $$$\log_2(m)$$$ values are set equal to $$$1$$$.
• Five additional values are chosen randomly from $$$[1, 6]$$$ so that the total sum stays below $$$60$$$.
Some intuition on the construction. The choice of $$$a_1, \dots, a_{h}$$$ may seem arbitrary; let us try to justify it. The goal is to generate a set of values $$$f(0), f(1),\dots, f(29)$$$ that are simultaneously "random enough" and with size smaller but comparable to $$$m$$$. These two conditions are necessary to expect that the backpacking problem finds a solution with high enough probability.
If $$$a_1=a_2=\cdots=a_{h}=1$$$, then $$$f(s) = \binom{k-h}{s}$$$ and these numbers have size comparable to $$$m$$$ if $$$2^{h}$$$ is comparable to $$$m$$$. This observation explains why we start with approximately $$$\log_2(m)$$$ ones. The issue is that we need some flexibility in the process as we may need to repeat it many times, this flexibility is provided by the addition of some additional random elements which don't change the magnitude of the values $$$f(0), f(1), \dots, f(29)$$$ but that modify them as much as possible (if we added a large number it would not affect many $$$f(s)$$$ and thus it would not be very useful).