Cute Sequences
Contest: Codeforces Round 561 (Div. 2)
Difficulty rating: 2200
Tags: binary search, brute force, greedy, math

Given a positive integer $$$m$$$, we say that a sequence $$$x_1, x_2, \dots, x_n$$$ of positive integers is $$$m$$$-cute if for every index $$$i$$$ such that $$$2 \le i \le n$$$ it holds that $$$x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$$$ for some positive integer $$$r_i$$$ satisfying $$$1 \le r_i \le m$$$.

You will be given $$$q$$$ queries consisting of three positive integers $$$a$$$, $$$b$$$ and $$$m$$$. For each query you must determine whether or not there exists an $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$. If such a sequence exists, you must additionally find an example of it.

Input format:
The first line contains an integer number $$$q$$$ ($$$1 \le q \le 10^3$$$) — the number of queries.

Each of the following $$$q$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$m$$$ ($$$1 \le a, b, m \le 10^{14}$$$, $$$a \leq b$$$), describing a single query.

Output format:
For each query, if no $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$ exists, print $$$-1$$$.

Otherwise print an integer $$$k$$$ ($$$1 \le k \leq 50$$$), followed by $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le 10^{14}$$$). These integers must satisfy $$$x_1 = a$$$, $$$x_k = b$$$, and that the sequence $$$x_1, x_2, \dots, x_k$$$ is $$$m$$$-cute.

It can be shown that under the problem constraints, for each query either no $$$m$$$-cute sequence exists, or there exists one with at most $$$50$$$ terms.

If there are multiple possible sequences, you may print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Consider the sample. In the first query, the sequence $$$5, 6, 13, 26$$$ is valid since $$$6 = 5 + \bf{\color{blue} 1}$$$, $$$13 = 6 + 5 + {\bf\color{blue} 2}$$$ and $$$26 = 13 + 6 + 5 + {\bf\color{blue} 2}$$$ have the bold values all between $$$1$$$ and $$$2$$$, so the sequence is $$$2$$$-cute. Other valid sequences, such as $$$5, 7, 13, 26$$$ are also accepted.

In the second query, the only possible $$$1$$$-cute sequence starting at $$$3$$$ is $$$3, 4, 8, 16, \dots$$$, which does not contain $$$9$$$.

Example input:
2
5 26 2
3 9 1

Example output:
4 5 6 13 26
-1

Editorial:
We will first deal with determining when the sequence doesn't exist. To do this, we place some bounds on the values of $$$x_n$$$. If we choose all values of the $$$r_i$$$ to be equal to $$$1$$$ then we can calculate that $$$x_n = 2^{n - 2}(x_1 + 1)$$$. Reciprocally if we choose all $$$r_i$$$ to be equal to $$$m$$$ then we find $$$x_n = 2^{n - 2}(x_1 + m)$$$. All other values give something inbetween, so we get
$$$$$$2^{n - 2}(x_1 + 1) \le x_n \le 2^{n - 2}(x_1 + m)$$$$$$
Therefore, if $$$b$$$ doesn't lie on any of the intervals $$$[2^{n - 2}(a + 1), 2^{n - 2}(a + m)]$$$ for some value of $$$n$$$, then it is impossible for $$$b$$$ to be a term of an $$$m$$$-cute sequence starting at $$$a$$$. This can be checked naively in $$$\mathcal{O}(\log(10^{14}))$$$ since there are this many relevant values of $$$n$$$. We can convince ourselves that all values in these intervals are feasible through some experimentation, so we now turn to the more difficult problem of actually constructing a sequence.
First, notice that we can rearrange the definition of the sequence as follows:
$$$$$$x_n = x_1 + x_2 + \dots + x_{n - 1} + r_n = (x_1 + \dots + x_{n - 2}) + x_{n - 1} + r_n \\ = (x_{n - 1} - r_{n - 1}) + x_{n - 1} + r_n = 2x_{n - 1} + r_n - r_{n - 1}$$$$$$
Now, we can try to find a pattern. We see that $$$x_2 = a + r_1$$$, $$$x_3 = 2a + r_1 + r_2$$$, $$$x_4 = 4a + 2r_1 + r_2 + r_3$$$, and in general it would seem that.
$$$$$$x_n = 2^{n - 2}a + 2^{n - 3}r_2 + 2^{n - 4}r_3 + \dots + 2r_{n - 2} + r_{n - 1} + r_n$$$$$$
This is actually very easy to prove inductively using $$$x_n = 2x_{n - 1} + r_n - r_{n - 1}$$$: All coefficients double from one term to the next, but we substract $$$r_{n - 1}$$$ once, so that coefficient becomes $$$1$$$ instead. Now we can also find an explicit solution: Write $$$b$$$ as $$$2^{n - 2}(a + k) + r$$$ where $$$r < 2^{n - 2}$$$, and consider the binary representation $$$r = d_{n - 3}d_{n - 4} \dots d_0$$$ of $$$r$$$. Then choosing $$$r_i = k + d_{n - 1 - i}$$$ (where $$$d_{-1} = 0$$$) works, because
$$$$$$2^{n - 2}a + 2^{n - 3}(k + d_{n - 3}) + \dots + 2(k + d_1) + (k + d_0) + k \\ = 2^{n - 2}a + (2^{n - 3} + 2^{n - 4} + \dots + 2 + 1 + 1)k + 2^{n - 3}d_{n - 3} + 2^{n - 4}d_{n - 4} + \dots + d_0 \\ = 2^{n - 2}a + 2^{n - 2}k + r \\ = 2^{n - 2}(a + k) + r$$$$$$
Alternatively, after getting the formula, we can iterate on $$$i$$$ from $$$2$$$ to $$$k$$$ and greedily choose the values of $$$r_i$$$ to be as large as we can without exceeding $$$b$$$. This can be easily shown to work using that the coefficients are consecutive powers of two.
Both of these approaches can be implemented in $$$\mathcal{O}(\log(10^{14}))$$$ per query.
Complexity: $$$\mathcal{O}(q\log(10^{14}))$$$