To Make 1
Contest: Technocup 2020 - Elimination Round 2
Difficulty rating: 3100
Tags: bitmasks, constructive algorithms, dp, greedy, number theory

There are $$$n$$$ positive integers written on the blackboard. Also, a positive number $$$k \geq 2$$$ is chosen, and none of the numbers on the blackboard are divisible by $$$k$$$. In one operation, you can choose any two integers $$$x$$$ and $$$y$$$, erase them and write one extra number $$$f(x + y)$$$, where $$$f(x)$$$ is equal to $$$x$$$ if $$$x$$$ is not divisible by $$$k$$$, otherwise $$$f(x) = f(x / k)$$$.

In the end, there will be a single number of the blackboard. Is it possible to make the final number equal to $$$1$$$? If so, restore any sequence of operations to do so.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ — the initial number of integers on the blackboard, and the chosen number ($$$2 \leq n \leq 16$$$, $$$2 \leq k \leq 2000$$$).

The second line contains $$$n$$$ positive integers $$$a_1, \ldots, a_n$$$ initially written on the blackboard. It is guaranteed that none of the numbers $$$a_i$$$ is divisible by $$$k$$$, and the sum of all $$$a_i$$$ does not exceed $$$2000$$$.

Output format:
If it is impossible to obtain $$$1$$$ as the final number, print "NO" in the only line.

Otherwise, print "YES" on the first line, followed by $$$n - 1$$$ lines describing operations. The $$$i$$$-th of these lines has to contain two integers $$$x_i$$$ and $$$y_i$$$ to be erased and replaced with $$$f(x_i + y_i)$$$ on the $$$i$$$-th operation. If there are several suitable ways, output any of them.

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

Note:
In the second sample case:

- $$$f(8 + 7) = f(15) = f(5) = 5$$$;
- $$$f(23 + 13) = f(36) = f(12) = f(4) = 4$$$;
- $$$f(5 + 4) = f(9) = f(3) = f(1) = 1$$$.

Example input:
2 2
1 1

Example output:
YES
1 1

Example input:
4 3
7 8 13 23

Example output:
YES
23 13
8 7
5 4

Editorial:
An experienced eye will immediately spot a subset dynamic programming solution in roughly $$$O(3^n \sum a_i)$$$ time, but the time constraints will not allow this. What to do?
Suppose there is a way to obtain 1 in the end. Looking at how many times each initial number $$$a_i$$$ gets divided by $$$k$$$ (including the divisions of the subsequent numbers containing it), we can obtain the expression $$$1 = \sum_{i = 1}^n a_i k^{-b_i}$$$, where $$$b_i$$$ are respective numbers of divisions. What if we were given such an expression to start with? Can we always restore a sequence of operations?
As it turns out, yes! Prove by induction. If there a single number, then it must be $$$1$$$ and we are done. Otherwise, let $$$B = \max b_i$$$. We argue that there are at least two numbers $$$a_i$$$ and $$$a_j$$$ with $$$b_i = b_j = B$$$. Indeed, assume there was only one such number $$$a_j$$$. Multiply both sides of the expression to obtain $$$k^B = \sum_{i = 1}^n a_i k^{B - b_i}$$$. The left-hand side, and all but one summand of the right-hand are divisible by $$$k$$$. But since $$$a_j$$$ is not divisible by $$$k$$$, the right-hand side is not divisible by $$$k$$$, a contradiction.
Since we have two numbers $$$a_i$$$ and $$$a_j$$$, let's replace them with $$$f(a_i + a_j) = a'$$$, and put $$$b' = B - (\text{the number of times }(a_i + a_j)\text{ is divisible by }k)$$$. We can see that the new set of numbers still satisfies the expression above, hence by induction hypothesis we can always finish the operation sequence. Note that this argument can be converted into an answer restoration routine: given the numbers $$$b_i$$$, group any pair of numbers $$$a_i$$$ and $$$a_j$$$ with $$$b_i = b_j$$$.
The question now becomes: can we find suitable numbers $$$b_1, \ldots, b_n$$$ such that the above expression is satisfied? We can do this with a more refined subset dynamic programming. For a subset $$$S \subseteq \{1, \ldots, n\}$$$ and a number $$$x$$$, let $$$dp_{S, x}$$$ be true if and only if we can have an expression $$$x = \sum_{i \in S} a_i k^{-b_i}$$$ for suitable $$$b_i$$$. The initial state is $$$dp_{\varnothing, 0} = 1$$$. The transitions are as follows:
• include $$$a_i$$$ into $$$S$$$: $$$dp_{S, x} \implies dp_{S + a_i, x + a_i}$$$;
• increase all $$$b_i$$$ by 1: if $$$x$$$ is divisible by $$$k$$$, then $$$dp_{S, x} \implies dp_{S, x / k}$$$.
By definition, we can obtain 1 as the final number iff $$$dp_{\{1, \ldots, n\}, 1}$$$. Straightforward recalculation requires $$$O(n 2^n \cdot \sum a_i)$$$ time. However, the first type of transition can be optimized using bitsets, bringing the complexity down to $$$O(2^n \sum a_i \cdot (1 + n / w))$$$, where $$$w$$$ is the size of the machine word ($$$32$$$ or $$$64$$$). To restore $$$b_i$$$, trace back from $$$dp_{\{1, \ldots, n\}, 1}$$$ to $$$dp_{\varnothing, 0}$$$ using reachable states.