codeforces-scrape

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

2106D.md (3517B)


      1 Source: https://codeforces.com/problemset/problem/2106/D
      2 
      3 D. Flower Boy
      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 Flower boy has a garden of $n$ flowers that can be represented as an integer sequence $a_1, a_2, \dots, a_n$, where $a_i$ is the beauty of the $i$-th flower from the left.
     22 
     23 Igor wants to collect exactly $m$ flowers. To do so, he will walk the garden from left to right and choose whether to collect the flower at his current position. The $i$-th flower among ones he collects must have a beauty of at least $b_i$.
     24 
     25 Igor noticed that it might be impossible to collect $m$ flowers that satisfy his beauty requirements, so before he starts collecting flowers, he can pick any integer $k$ and use his magic wand to grow a new flower with beauty $k$ and place it anywhere in the garden (between two flowers, before the first flower, or after the last flower). Because his magic abilities are limited, he may do this at most once.
     26 
     27 Output the minimum integer $k$ Igor must pick when he performs the aforementioned operation to ensure that he can collect $m$ flowers. If he can collect $m$ flowers without using the operation, output $0$. If it is impossible to collect $m$ flowers despite using the operation, output $-1$.
     28 
     29 Input
     30 
     31 The first line of the input contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases.
     32 
     33 The first line of each test case contains exactly two integers $n$ and $m$ $(1 \le m \le n \le 2 \cdot 10^5)$ — the number of flowers in the garden and the number of flowers Igor wants to collect, respectively.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ — where $a_i$ is the beauty of the $i$-th flower from the left in the garden.
     36 
     37 The third line of each test case contains $m$ integers $b_1, b_2, ..., b_m$ $(1 \le b_i \le 10^9)$ — where $b_i$ is the minimum beauty the $i$-th flower must have that Igor will collect.
     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, on a separate line, output the minimum integer $k$ Igor must pick when he performs the aforementioned operation to ensure that he can collect $m$ flowers. If he can collect $m$ flowers without using the operation, output $0$. If it is impossible to collect $m$ flowers despite using the operation, output $-1$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 7
     51 
     52 9 5
     53 
     54 3 5 2 3 3 5 8 1 2
     55 
     56 4 6 2 4 6
     57 
     58 6 3
     59 
     60 1 2 6 8 2 1
     61 
     62 5 4 3
     63 
     64 5 3
     65 
     66 4 3 5 4 3
     67 
     68 7 4 5
     69 
     70 6 3
     71 
     72 8 4 2 1 2 5
     73 
     74 6 1 4
     75 
     76 5 5
     77 
     78 1 2 3 4 5
     79 
     80 5 4 3 2 1
     81 
     82 6 3
     83 
     84 1 2 3 4 5 6
     85 
     86 9 8 7
     87 
     88 5 5
     89 
     90 7 7 6 7 7
     91 
     92 7 7 7 7 7
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 6
     99 3
    100 7
    101 0
    102 -1
    103 -1
    104 7
    105 ```
    106 
    107 Note
    108 
    109 In the first test case, suppose Igor grows a flower of beauty $6$ and places it between the third and the fourth flowers. Then, the garden will look like the following: $[3, 5, 2, 6, 3, 3, 5, 8, 1, 2]$. Then, he can select the second, fourth, sixth, seventh, and eighth flowers with beauties $[5, 6, 3, 5, 8]$.
    110 
    111 In the third test case, he can grow a flower of beauty $7$ and place it before the first flower. The garden will look like the following: $[7, 4, 3, 5, 4, 3]$. Now, he can choose the first, second, and fourth flowers.
    112 
    113 In the fourth test case, Igor does not need to use the operation, so the answer is $0$.
    114 
    115 In the sixth test case, no matter how Igor performs the operation, he cannot collect $3$ flowers such that the $i$-th flower he collects has a beauty of at least $b_i$, therefore the answer is $-1$.