codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.