codeforces-scrape

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

1671B.md (2100B)


      1 Source: https://codeforces.com/problemset/problem/1671/B
      2 
      3 B. Consecutive Points Segment
      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 You are given $n$ points with integer coordinates on a coordinate axis $OX$. The coordinate of the $i$-th point is $x_i$. All points' coordinates are distinct and given in strictly increasing order.
     22 
     23 For each point $i$, you can do the following operation no more than once: take this point and move it by $1$ to the left or to the right (i..e., you can change its coordinate $x_i$ to $x_i - 1$ or to $x_i + 1$). In other words, for each point, you choose (separately) its new coordinate. For the $i$-th point, it can be either $x_i - 1$, $x_i$ or $x_i + 1$.
     24 
     25 Your task is to determine if you can move some points as described above in such a way that the new set of points forms a consecutive segment of integers, i. e. for some integer $l$ the coordinates of points should be equal to $l, l + 1, \ldots, l + n - 1$.
     26 
     27 Note that the resulting points should have distinct coordinates.
     28 
     29 You have to answer $t$ independent test cases.
     30 
     31 Input
     32 
     33 The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.
     34 
     35 The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of points in the set $x$.
     36 
     37 The second line of the test case contains $n$ integers $x_1 \lt x_2 \lt \ldots \lt x_n$ ($1 \le x_i \le 10^6$), where $x_i$ is the coordinate of the $i$-th point.
     38 
     39 It is guaranteed that the points are given in strictly increasing order (this also means that all coordinates are distinct). It is also guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).
     40 
     41 Output
     42 
     43 For each test case, print the answer — if the set of points from the test case can be moved to form a consecutive segment of integers, print YES, otherwise print NO.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 2
     53 
     54 1 4
     55 
     56 3
     57 
     58 1 2 3
     59 
     60 4
     61 
     62 1 2 3 7
     63 
     64 1
     65 
     66 1000000
     67 
     68 3
     69 
     70 2 5 6
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 YES
     77 YES
     78 NO
     79 YES
     80 YES
     81 ```