codeforces-scrape

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

1713B.md (1965B)


      1 Source: https://codeforces.com/problemset/problem/1713/B
      2 
      3 B. Optimal Reduction
      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 Consider an array $a$ of $n$ positive integers.
     22 
     23 You may perform the following operation:
     24 
     25 * select two indices $l$ and $r$ ($1 \leq l \leq r \leq n$), then
     26 * decrease all elements $a_l, a_{l + 1}, \dots, a_r$ by $1$.
     27 
     28 Let's call $f(a)$ the minimum number of operations needed to change array $a$ into an array of $n$ zeros.
     29 
     30 Determine if for all permutations$^\dagger$ $b$ of $a$, $f(a) \leq f(b)$ is true.
     31 
     32 $^\dagger$ An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$.
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.
     39 
     40 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — description of the array $a$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, print "YES" (without quotes) if for all permutations $b$ of $a$, $f(a) \leq f(b)$ is true, and "NO" (without quotes) otherwise.
     47 
     48 You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 3
     56 
     57 4
     58 
     59 2 3 5 4
     60 
     61 3
     62 
     63 1 2 3
     64 
     65 4
     66 
     67 3 1 3 2
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 YES
     74 YES
     75 NO
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, we can change all elements to $0$ in $5$ operations. It can be shown that no permutation of $[2, 3, 5, 4]$ requires less than $5$ operations to change all elements to $0$.
     81 
     82 In the third test case, we need $5$ operations to change all elements to $0$, while $[2, 3, 3, 1]$ only needs $3$ operations.