codeforces-scrape

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

1557B.md (2301B)


      1 Source: https://codeforces.com/problemset/problem/1557/B
      2 
      3 B. Moamen and k-subarrays
      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 Moamen has an array of $n$ distinct integers. He wants to sort that array in non-decreasing order by doing the following operations in order exactly once:
     22 
     23 1. Split the array into exactly $k$ non-empty subarrays such that each element belongs to exactly one subarray.
     24 2. Reorder these subarrays arbitrary.
     25 3. Merge the subarrays in their new order.
     26 
     27 A sequence $a$ is a subarray of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
     28 
     29 Can you tell Moamen if there is a way to sort the array in non-decreasing order using the operations written above?
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. The description of the test cases follows.
     34 
     35 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$).
     36 
     37 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le |a_i| \le 10^9$). It is guaranteed that all numbers are distinct.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.
     40 
     41 Output
     42 
     43 For each test case, you should output a single string.
     44 
     45 If Moamen can sort the array in non-decreasing order, output "YES" (without quotes). Otherwise, output "NO" (without quotes).
     46 
     47 You can print each letter of "YES" and "NO" in any case (upper or lower).
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 5 4
     56 6 3 4 2 1
     57 4 2
     58 1 -4 0 -2
     59 5 1
     60 1 2 3 4 5
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 Yes
     67 No
     68 Yes
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, $a = [6, 3, 4, 2, 1]$, and $k = 4$, so we can do the operations as follows:
     74 
     75 1. Split $a$ into $\{ [6], [3, 4], [2], [1] \}$.
     76 2. Reorder them: $\{ [1], [2], [3,4], [6] \}$.
     77 3. Merge them: $[1, 2, 3, 4, 6]$, so now the array is sorted.
     78 
     79 In the second test case, there is no way to sort the array by splitting it into only $2$ subarrays.
     80 
     81 As an example, if we split it into $\{ [1, -4], [0, -2] \}$, we can reorder them into $\{ [1, -4], [0, -2] \}$ or $\{ [0, -2], [1, -4] \}$. However, after merging the subarrays, it is impossible to get a sorted array.