Points and Powers of Two
Contest: Codeforces Round 486 (Div. 3)
Difficulty rating: 1800
Tags: brute force, math

There are $$$n$$$ distinct points on a coordinate line, the coordinate of $$$i$$$-th point equals to $$$x_i$$$. Choose a subset of the given set of points such that the distance between each pair of points in a subset is an integral power of two. It is necessary to consider each pair of points, not only adjacent. Note that any subset containing one element satisfies the condition above. Among all these subsets, choose a subset with maximum possible size.

In other words, you have to choose the maximum possible number of points $$$x_{i_1}, x_{i_2}, \dots, x_{i_m}$$$ such that for each pair $$$x_{i_j}$$$, $$$x_{i_k}$$$ it is true that $$$|x_{i_j} - x_{i_k}| = 2^d$$$ where $$$d$$$ is some non-negative integer number (not necessarily the same for each pair of points).

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points.

The second line contains $$$n$$$ pairwise distinct integers $$$x_1, x_2, \dots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$) — the coordinates of points.

Output format:
In the first line print $$$m$$$ — the maximum possible number of points in a subset that satisfies the conditions described above.

In the second line print $$$m$$$ integers — the coordinates of points in the subset you have chosen.

If there are multiple answers, print any of them.

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

Note:
In the first example the answer is $$$[7, 3, 5]$$$. Note, that $$$|7-3|=4=2^2$$$, $$$|7-5|=2=2^1$$$ and $$$|3-5|=2=2^1$$$. You can't find a subset having more points satisfying the required property.

Example input:
6
3 5 4 7 10 12

Example output:
3
7 3 5

Example input:
5
-1 2 5 8 11

Example output:
1
8

Editorial:
Firstly, let's prove that the size of the answer is not greater than $$$3$$$. Suppose that the answer equals to $$$4$$$. Let $$$a, b, c, d$$$ be coordinates of the points in the answer (and $$$a < b < c < d$$$). Let $$$dist(a, b) = 2^k$$$ and $$$dist(b, c) = 2^l$$$. Then $$$dist(a, c) = dist(a, b) + dist(b, c) = 2^k + 2^l = 2^m$$$ (because of the condition). It means that $$$k = l$$$. Conditions must hold for a triple $$$b, c, d$$$ too. Now it is easy to see that if $$$dist(a, b) = dist(b, c) = dist(c, d) = 2^k$$$ then $$$dist(a, d) = dist(a, b) * 3$$$ that is not a power of two. So the size of the answer is not greater than $$$3$$$.
Firstly, let's check if the answer is $$$3$$$. Iterate over all middle elements of the answer and over all powers of two from $$$0$$$ to $$$30$$$ inclusively. Let $$$x_i$$$ be the middle element of the answer and $$$j$$$ — the current power of two. Then if there are elements $$$x_i - 2^j$$$ and $$$x_i + 2^j$$$ in the array then the answer is $$$3$$$.
Now check if the answer is $$$2$$$. Do the same as in the previous solution, but now we have left point $$$x_i$$$ and right point $$$x_i + 2^j$$$.
If we did not find answer of lengths $$$3$$$ or $$$2$$$ then print any element of the array.
The solution above have time complexity $$$O(n \cdot \log n \cdot \log 10^9)$$$ (because of we can check if the element is in the array with some data structure in $$$O(\log n)$$$).