1364B.md (2099B)
1 Source: https://codeforces.com/problemset/problem/1364/B 2 3 B. Most socially-distanced subsequence 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given a permutation $p$ of length $n$, find its subsequence $s_1$, $s_2$, $\ldots$, $s_k$ of length at least $2$ such that: 22 23 * $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ is as big as possible over all subsequences of $p$ with length at least $2$. 24 * Among all such subsequences, choose the one whose length, $k$, is as small as possible. 25 26 If multiple subsequences satisfy these conditions, you are allowed to find any of them. 27 28 A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deleting some (possibly, zero or all) elements. 29 30 A permutation of length $n$ is an array of length $n$ in which every element from $1$ to $n$ occurs exactly once. 31 32 Input 33 34 The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows. 35 36 The first line of each test case contains an integer $n$ ($2 \le n \le 10^5$) — the length of the permutation $p$. 37 38 The second line of each test case contains $n$ integers $p_1$, $p_2$, $\ldots$, $p_{n}$ ($1 \le p_i \le n$, $p_i$ are distinct) — the elements of the permutation $p$. 39 40 The sum of $n$ across the test cases doesn't exceed $10^5$. 41 42 Output 43 44 For each test case, the first line should contain the length of the found subsequence, $k$. The second line should contain $s_1$, $s_2$, $\ldots$, $s_k$ — its elements. 45 46 If multiple subsequences satisfy these conditions, you are allowed to find any of them. 47 48 Example 49 50 Input 51 52 ``` 53 2 54 3 55 3 2 1 56 4 57 1 3 4 2 58 ``` 59 60 Output 61 62 ``` 63 2 64 3 1 65 3 66 1 4 2 67 ``` 68 69 Note 70 71 In the first test case, there are $4$ subsequences of length at least $2$: 72 73 * $[3,2]$ which gives us $|3-2|=1$. 74 * $[3,1]$ which gives us $|3-1|=2$. 75 * $[2,1]$ which gives us $|2-1|=1$. 76 * $[3,2,1]$ which gives us $|3-2|+|2-1|=2$. 77 78 So the answer is either $[3,1]$ or $[3,2,1]$. Since we want the subsequence to be as short as possible, the answer is $[3,1]$.