codeforces-scrape

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

2220B.md (2920B)


      1 Source: https://codeforces.com/problemset/problem/2220/B
      2 
      3 B. OIE Excursion
      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 Hector is on an excursion with the Spanish Olympiad in Informatics, visiting A Coruña, but he is desperate to sneak away to meet his friends Gustavo, Esomer, and Dani. To do so, he must cross a path guarded by $n$ volunteers standing in a row, numbered from $1$ to $n$; the $i$-th volunteer watches over position $i$.
     22 
     23 Each volunteer has an internal timer. Initially (at second $0$), the $i$-th volunteer's timer has a value $a_i$. Every second, all timers increase by $1$. Once a timer reaches $m$, it wraps around to $0$. Specifically, at second $x$, the $i$-th volunteer's timer shows the value $(a_i + x) \pmod m$.
     24 
     25 The $i$-th volunteer is only watching over position $i$ when their timer is exactly $0$. At any other time, they are distracted and will not notice Hector.
     26 
     27 Hector starts at position $0$, to the left of all volunteers. To escape, he must reach position $n+1$. In the end of each second, Hector can choose to stay in his current position, move one position to the left, or move one position to the right. Note that Hector can't go to the left of position $0$.
     28 
     29 Hector is caught if and only if, at the beginning of a second, he is at position $i$ ($1 \le i \le n$) and the $i$-th volunteer's timer is $0$.
     30 
     31 Determine whether there exists a strategy for Hector to pass all volunteers and escape without being caught.
     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^4$). The description of the test cases follows.
     36 
     37 Each test case consists of two lines:
     38 
     39 * The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $2 \le m \le 10^9$) — the number of volunteers and the cycle length of the timers.
     40 * The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt m$), where $a_i$ represents the initial value of the $i$-th volunteer's timer at $t=0$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, print a line containing either "YES" or "NO", representing whether Hector can escape. 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.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 8 5
     56 
     57 0 4 0 2 1 0 0 3
     58 
     59 6 2
     60 
     61 1 0 1 0 1 0
     62 
     63 6 2
     64 
     65 1 1 1 1 0 1
     66 
     67 2 10
     68 
     69 6 9
     70 
     71 2 2
     72 
     73 0 1
     74 
     75 5 1000000000
     76 
     77 1 2 3 4 999999999
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 YES
     84 
     85 YES
     86 
     87 NO
     88 
     89 YES
     90 
     91 YES
     92 
     93 YES
     94 ```
     95 
     96 Note
     97 
     98 * Case 1: Hector can move right every second without waiting or moving left and escape, because there is no $i$ such that $(a_i + i) \pmod m = 0$.
     99 * Case 2: One possible strategy is to wait for one second at the starting position and then move right every second without further waiting or moving left.