codeforces-scrape

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

2126C.md (2728B)


      1 Source: https://codeforces.com/problemset/problem/2126/C
      2 
      3 C. I Will Definitely Make It
      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 $n$ towers, numbered from $1$ to $n$. Tower $i$ has a height of $h_i$. At time $0$, you are on the tower with index $k$, and the current water level is $1$.
     22 
     23 Every second, the water level rises by $1$ unit. At any moment, if the water level becomes strictly greater than the height of the tower you are on, you perish.
     24 
     25 You have a magical ability: at moment $x$, you can start teleporting from tower $i$ to tower $j$, which will take $\lvert h_i - h_j \rvert$ seconds. That is, until moment $x + \lvert h_i - h_j \rvert$, you will be on tower $i$, and at moment $x + \lvert h_i - h_j \rvert$, you will move to tower $j$. You can start a new teleportation at the same moment you just arrived at tower $j$.
     26 
     27 For example, if $n=k=4$, $h=[4, 4, 4, 2]$, then if you start teleporting from tower $4$ to tower $1$ at moment $0$, the movement will look as follows:
     28 
     29  ![](https://espresso.codeforces.com/93a9fcf710028ea862e93a2ab50ac2f9ba42b212.png) 
     30 
     31 Note that if the height of tower $1$ were $5$, you would not be able to teleport to it immediately, as you would be submerged at moment $2$.
     32 
     33 Your goal is to reach any tower with the maximum height before the water covers you.
     34 
     35 Determine if this is possible.
     36 
     37 Input
     38 
     39 Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     40 
     41 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the number of towers and the index of the tower you are initially on.
     42 
     43 The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$) — the heights of the towers.
     44 
     45 It is guaranteed that the sum of all $n$ across all test cases does not exceed $10^5$.
     46 
     47 Output
     48 
     49 For each test case, output one line: "YES", if you can reach the tower with the maximum height before the water covers you, or "NO" otherwise.
     50 
     51 You may output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 5
     59 
     60 5 3
     61 
     62 3 2 1 4 5
     63 
     64 3 1
     65 
     66 1 3 4
     67 
     68 4 4
     69 
     70 4 4 4 2
     71 
     72 6 2
     73 
     74 2 3 6 9 1 2
     75 
     76 4 2
     77 
     78 1 2 5 6
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 YES
     85 NO
     86 YES
     87 YES
     88 NO
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, the only possible path is: $3 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 5$.
     94 
     95 In the second test case, regardless of the order, it will not be possible to reach the tallest tower.
     96 
     97 In the third test case, one of the possible paths is: $4 \rightarrow 1$.