codeforces-scrape

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

2032B.md (3460B)


      1 Source: https://codeforces.com/problemset/problem/2032/B
      2 
      3 B. Medians
      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 You are given an array $a = [1, 2, \ldots, n]$, where $n$ is odd, and an integer $k$.
     22 
     23 Your task is to choose an odd positive integer $m$ and to split $a$ into $m$ subarrays$^{\dagger}$ $b_1, b_2, \ldots, b_m$ such that:
     24 
     25 * Each element of the array $a$ belongs to exactly one subarray.
     26 * For all $1 \le i \le m$, $|b_i|$ is odd, i.e., the length of each subarray is odd.
     27 * $\operatorname{median}([\operatorname{median}(b_1), \operatorname{median}(b_2), \ldots, \operatorname{median}(b_m)]) = k$, i.e., the median$^{\ddagger}$ of the array of medians of all subarrays must equal $k$. $\operatorname{median}(c)$ denotes the median of the array $c$.
     28 
     29 $^{\dagger}$A subarray of the array $a$ of length $n$ is the array $[a_l, a_{l + 1}, \ldots, a_r]$ for some integers $1 \le l \le r \le n$.
     30 
     31 $^{\ddagger}$A median of the array of odd length is the middle element after the array is sorted in non-decreasing order. For example: $\operatorname{median}([1,2,5,4,3]) = 3$, $\operatorname{median}([3,2,1]) = 2$, $\operatorname{median}([2,1,2,1,2,2,2]) = 2$.
     32 
     33 Input
     34 
     35 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 5000$) — the number of test cases. The description of the test cases follows.
     36 
     37 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \lt 2 \cdot 10^5$, $n$ is odd) — the length of array $a$ and the desired median of the array of medians of all subarrays.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case:
     44 
     45 * If there is no suitable partition, output $-1$ in a single line.
     46 * Otherwise, in the first line, output an odd integer $m$ ($1 \le m \le n$), and in the second line, output $m$ distinct integers $p_1, p_2 , p_3 , \ldots, p_m$ ($1 = p_1 \lt p_2 \lt p_3 \lt \ldots \lt p_m \le n$) — denoting the left borders of each subarray.
     47 
     48 In detail, for a valid answer $[p_1, p_2, \ldots, p_m]$:
     49 
     50 * $b_1 = \left[ a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1} \right]$
     51 * $b_2 = \left[ a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1} \right]$
     52 * $\ldots$
     53 * $b_m = \left[ a_{p_m}, a_{p_m + 1}, \ldots, a_n \right]$.
     54 
     55 If there are multiple solutions, you can output any of them.
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 4
     63 
     64 1 1
     65 
     66 3 2
     67 
     68 3 3
     69 
     70 15 8
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1
     77 1
     78 3
     79 1 2 3
     80 -1
     81 5
     82 1 4 7 10 13
     83 ```
     84 
     85 Note
     86 
     87 In the first test case, the given partition has $m = 1$ and $b_1 = [1]$. It is obvious that $\operatorname{median}([\operatorname{median}([1])]) = \operatorname{median}([1]) = 1$.
     88 
     89 In the second test case, the given partition has $m = 3$ and:
     90 
     91 * $b_1 = [1]$
     92 * $b_2 = [2]$
     93 * $b_3 = [3]$
     94 
     95 Therefore, $\operatorname{median}([\operatorname{median}([1]), \operatorname{median}([2]), \operatorname{median}([3])]) = \operatorname{median}([1, 2, 3]) = 2$.
     96 
     97 In the third test case, there is no valid partition for $k = 3$.
     98 
     99 In the fourth test case, the given partition has $m = 5$ and:
    100 
    101 * $b_1 = [1, 2, 3]$
    102 * $b_2 = [4, 5, 6]$
    103 * $b_3 = [7, 8, 9]$
    104 * $b_4 = [10, 11, 12]$
    105 * $b_5 = [13, 14, 15]$
    106 
    107 Therefore, $\operatorname{median}([\operatorname{median}([1, 2, 3]), \operatorname{median}([4, 5, 6]), \operatorname{median}([7, 8, 9]), \operatorname{median}([10, 11, 12]), \operatorname{median}([13, 14, 15])]) = \operatorname{median}([2, 5, 8, 11, 14]) = 8$.