codeforces-scrape

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

2117D.md (1853B)


      1 Source: https://codeforces.com/problemset/problem/2117/D
      2 
      3 D. Retaliation
      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 Yousef wants to explode an array $a_1, a_2, \dots, a_n$. An array gets exploded when all of its elements become equal to zero.
     22 
     23 In one operation, Yousef can do exactly one of the following:
     24 
     25 1. For every index $i$ in $a$, decrease $a_i$ by $i$.
     26 2. For every index $i$ in $a$, decrease $a_i$ by $n - i + 1$.
     27 
     28 Your task is to help Yousef determine if it is possible to explode the array using any number of operations.
     29 
     30 Input
     31 
     32 The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     33 
     34 The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of the array.
     35 
     36 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.
     37 
     38 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, print "YES" if Yousef can explode the array, otherwise output "NO".
     43 
     44 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.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 6
     52 
     53 4
     54 
     55 3 6 6 3
     56 
     57 5
     58 
     59 21 18 15 12 9
     60 
     61 10
     62 
     63 2 6 10 2 5 5 1 2 4 10
     64 
     65 7
     66 
     67 10 2 16 12 8 20 4
     68 
     69 2
     70 
     71 52 101
     72 
     73 2
     74 
     75 10 2
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 NO
     82 YES
     83 NO
     84 NO
     85 YES
     86 NO
     87 ```
     88 
     89 Note
     90 
     91 In the second test case, we can do the following:
     92 
     93 * Perform $1$ operation of the first type. The array becomes $[20, 16, 12, 8, 4]$.
     94 * Perform $4$ operations of the second type. The array becomes $[0, 0, 0, 0, 0]$.
     95 
     96 In the first, third, fourth, and sixth test cases, it can be proven that it is impossible to make all elements equal to zero using any number of operations.