codeforces-scrape

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

2162E.md (2324B)


      1 Source: https://codeforces.com/problemset/problem/2162/E
      2 
      3 E. Beautiful Palindromes
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 We call an array $[b_1, b_2, \dots, b_m]$ of length $m$ palindromic if the following condition holds:
     22 
     23 * $b_i = b_{m-i+1}$ for all $1 \le i \le m$
     24 
     25 In other words, an array is palindromic if it reads the same forward and backward.
     26 
     27 You are given an array $[a_1, a_2, \dots , a_n]$ of $n$ integers where $1 \le a_i \le n$ and an integer $k$.
     28 
     29 You are required to perform the following operation exactly $k$ times:
     30 
     31 * choose an integer $x$ such that $1 \le x \le n$,
     32 * append $x$ to the end of the array $a$.
     33 
     34 Your goal is to perform these $k$ operations in such a way that the number of palindromic subarrays$^{\text{∗}}$ in the resulting array is minimized.
     35 
     36 Output the $k$ integers you chose for each operation, in the order they were appended.
     37 
     38 $^{\text{∗}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.
     39 
     40 Input
     41 
     42 The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     43 
     44 The first line of each test case contains two integers $n$ and $k$ ($3 \le n \le 2\cdot10^5, 1 \le k \le n$) — the length of the array $a$.
     45 
     46 The second line of each test case contains $n$ integers $a_1, a_2, \ldots , a_n$ ($1 \le a_i \le n$) — the elements of the array $a$.
     47 
     48 It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^5$.
     49 
     50 Output
     51 
     52 For each test case, print the $k$ integers chosen for the append operations, in the order they were appended, such that the total number of palindromic subarrays in the resulting array is minimized.
     53 
     54 If there are multiple answers, you may output any one of them.
     55 
     56 Example
     57 
     58 Input
     59 
     60 ```
     61 5
     62 
     63 4 1
     64 
     65 1 3 3 4
     66 
     67 4 2
     68 
     69 2 2 2 2
     70 
     71 5 1
     72 
     73 4 1 5 2 2
     74 
     75 6 3
     76 
     77 1 2 3 4 5 6
     78 
     79 5 3
     80 
     81 3 2 5 2 3
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 2
     88 
     89 1 3
     90 
     91 3
     92 
     93 3 4 1
     94 
     95 4 1 5
     96 ```
     97 
     98 Note
     99 
    100 For the first test case, if we append $2$ to the end of the array, $a$ becomes $[1, 3, 3, 4, 2]$. Now $a$ has only $6$ palindromic subarrays — $[1]$, $[3]$, $[3]$, $[4]$, $[2]$, $[3, 3]$.