D. Points and Powers of Two

Codeforces

IDCF988D

Time4000ms

Memory256MB

Difficulty—

brute forcemath

English · Original

Chinese · Translation

Formal · Original

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 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 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. [samples] ## 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.

在一条坐标轴上有 $n$ 个互不相同的点，第 $i$ 个点的坐标为 $x_i$。请从给定点集中选择一个子集，使得该子集中任意两点之间的距离均为 2 的整数次幂。需要考虑每一对点，而不仅仅是相邻点。注意，任何只包含一个元素的子集都满足上述条件。在所有满足条件的子集中，选择一个元素个数最多的子集。换句话说，你需要选择尽可能多的点 $x_{i_1}, x_{i_2}, dots.h, x_{i_m}$，使得对于每一对点 $x_{i_j}$ 和 $x_{i_k}$，都有 $| x_{i_j} - x_{i_k} | = 2^d$，其中 $d$ 是某个非负整数（每对点的 $d$ 不必相同）。第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^5$）——点的数量。第二行包含 $n$ 个两两不同的整数 $x_1, x_2, dots.h, x_n$（$-10^9 lt.eq x_i lt.eq 10^9$）——点的坐标。第一行输出 $m$ —— 满足上述条件的子集中可能的最大点数。第二行输出 $m$ 个整数 —— 你所选子集中点的坐标。如果有多个答案，输出任意一个即可。在第一个示例中，答案为 $[ 7, 3, 5 ]$。注意，$| 7 -3 | = 4 = 2^2$，$| 7 -5 | = 2 = 2^1$，且 $| 3 -5 | = 2 = 2^1$。无法找到包含更多点且满足要求的子集。 ## Input 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^5$）——点的数量。第二行包含 $n$ 个两两不同的整数 $x_1, x_2, dots.h, x_n$（$-10^9 lt.eq x_i lt.eq 10^9$）——点的坐标。 ## Output 第一行输出 $m$ —— 满足上述条件的子集中可能的最大点数。第二行输出 $m$ 个整数 —— 你所选子集中点的坐标。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个示例中，答案为 $[ 7, 3, 5 ]$。注意，$| 7 -3 | = 4 = 2^2$，$| 7 -5 | = 2 = 2^1$，且 $| 3 -5 | = 2 = 2^1$。无法找到包含更多点且满足要求的子集。

Let $ S = \{x_1, x_2, \dots, x_n\} \subset \mathbb{Z} $ be a set of $ n $ distinct integer coordinates. Define a graph $ G = (S, E) $, where an edge $ (x_i, x_j) \in E $ exists if and only if $ |x_i - x_j| = 2^d $ for some integer $ d \geq 0 $. The problem reduces to finding the **maximum clique** in $ G $: a subset $ C \subseteq S $ of maximum size such that for every pair $ x_i, x_j \in C $, $ |x_i - x_j| $ is a power of two. --- **Objective:** Find a maximum clique $ C \subseteq S $ in the graph $ G $ defined above. --- **Constraints:** - $ |S| = n $, $ 1 \leq n \leq 2 \cdot 10^5 $ - $ x_i \in \mathbb{Z} $, $ -10^9 \leq x_i \leq 10^9 $, all distinct - For any $ x_i, x_j \in C $, $ |x_i - x_j| \in \{2^d \mid d \in \mathbb{Z}_{\geq 0}\} $ --- **Output:** - $ m = |C| $ - The elements of $ C $, in any order.

Samples

Input #1

6
3 5 4 7 10 12

Output #1

3
7 3 5

Input #2

5
-1 2 5 8 11

Output #2

1
8

API Response (JSON)

{
  "problem": {
    "name": "D. Points and Powers of Two",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF988D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在一条坐标轴上有 $n$ 个互不相同的点，第 $i$ 个点的坐标为 $x_i$。请从给定点集中选择一个子集，使得该子集中任意两点之间的距离均为 2 的整数次幂。需要考虑每一对点，而不仅仅是相邻点。注意，任何只包含一个元素的子集都满足上述条件。在所有满足条件的子集中，选择一个元素个数最多的子集。\n\n换句话说，你需要选择尽可能多的点 $x_{i_1}, x_{i_2}, dots.h, x_{i_m}...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{Z} $ be a set of $ n $ distinct integer coordinates.\n\nDefine a graph $ G = (S, E) $, where an edge $ (x_i, x_j) \\in E $ exists if and only if $ |x_i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments