codeforces-scrape

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

2128C.md (2098B)


      1 Source: https://codeforces.com/problemset/problem/2128/C
      2 
      3 C. Leftmost Below
      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 Consider an array $a_1, \ldots, a_n$. Initially, $a_i = 0$ for every $i$.
     22 
     23 You can do operations of the following form.
     24 
     25 * You choose an integer $x$ greater than $\min(a)$.
     26 * Then, $i$ is defined as the minimum index such that $a_i \lt x$. In other words, $i$ is the unique integer between $1$ and $n$ inclusive such that $a_i \lt x$ and $a_j \geq x$ for every $1 \leq j \leq i-1$.
     27 * Finally, $a_i$ is incremented by $x$.
     28 
     29 For example, if $a = [6, 8, 2, 1]$ and you choose $x = 6$, then $i$ will be equal to $3$ (since $a_1 \geq 6$, $a_2 \geq 6$, and $a_3 \lt 6$) and $a$ will become $[6, 8, 8, 1]$.
     30 
     31 You can do as many operations as you want. Can you reach a target array $b_1, \ldots, b_n$?
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.
     36 
     37 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 200\,000$).
     38 
     39 The second line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$).
     40 
     41 The sum of $n$ over all test cases does not exceed $200\,000$.
     42 
     43 Output
     44 
     45 For each test case, print YES if you can reach the target array and NO otherwise.
     46 
     47 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 4
     57 
     58 5 6 1 1
     59 
     60 3
     61 
     62 3 1 2
     63 
     64 3
     65 
     66 40 60 90
     67 
     68 2
     69 
     70 1 1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 YES
     77 NO
     78 NO
     79 YES
     80 ```
     81 
     82 Note
     83 
     84 In the first test case, we can do the following sequence of operations:
     85 
     86 * we choose $x=2$, $a$ becomes $[2, 0, 0, 0]$
     87 * we choose $x=2$, $a$ becomes $[2, 2, 0, 0]$
     88 * we choose $x=3$, $a$ becomes $[5, 2, 0, 0]$
     89 * we choose $x=4$, $a$ becomes $[5, 6, 0, 0]$
     90 * we choose $x=1$, $a$ becomes $[5, 6, 1, 0]$
     91 * we choose $x=1$, $a$ becomes $[5, 6, 1, 1]$
     92 
     93 In the second test case, we can prove there is no way to reach $[3, 1, 2]$.