codeforces-scrape

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

1815A.md (2224B)


      1 Source: https://codeforces.com/problemset/problem/1815/A
      2 
      3 A. Ian and Array Sorting
      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 To thank Ian, Mary gifted an array $a$ of length $n$ to Ian. To make himself look smart, he wants to make the array in non-decreasing order by doing the following finitely many times: he chooses two adjacent elements $a_i$ and $a_{i+1}$ ($1\le i\le n-1$), and increases both of them by $1$ or decreases both of them by $1$. Note that, the elements of the array can become negative.
     22 
     23 As a smart person, you notice that, there are some arrays such that Ian cannot make it become non-decreasing order! Therefore, you decide to write a program to determine if it is possible to make the array in non-decreasing order.
     24 
     25 Input
     26 
     27 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.
     28 
     29 The first line of each test case consists of a single integer $n$ ($2\le n\le 3\cdot10^5$) — the number of elements in the array.
     30 
     31 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.
     32 
     33 It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.
     34 
     35 Output
     36 
     37 For each test case, output "YES" if there exists a sequence of operations which make the array non-decreasing, else output "NO".
     38 
     39 You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 
     48 3
     49 
     50 1 3 2
     51 
     52 2
     53 
     54 2 1
     55 
     56 4
     57 
     58 1 3 5 7
     59 
     60 4
     61 
     62 2 1 4 3
     63 
     64 5
     65 
     66 5 4 3 2 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 YES
     73 NO
     74 YES
     75 NO
     76 YES
     77 ```
     78 
     79 Note
     80 
     81 For the first test case, we can increase $a_2$ and $a_3$ both by $1$. The array is now $[1, 4, 3]$.
     82 
     83 Then we can decrease $a_1$ and $a_2$ both by $1$. The array is now $[0, 3, 3]$, which is sorted in non-decreasing order. So the answer is "YES".
     84 
     85 For the second test case, no matter how Ian perform the operations, $a_1$ will always be larger than $a_2$. So the answer is "NO" and Ian cannot pretend to be smart.
     86 
     87 For the third test case, the array is already in non-decreasing order, so Ian does not need to do anything.