codeforces-scrape

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

1375C.md (2349B)


      1 Source: https://codeforces.com/problemset/problem/1375/C
      2 
      3 C. Element Extermination
      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 an array $a$ of length $n$, which initially is a permutation of numbers from $1$ to $n$. In one operation, you can choose an index $i$ ($1 \leq i \lt n$) such that $a_i \lt a_{i + 1}$, and remove either $a_i$ or $a_{i + 1}$ from the array (after the removal, the remaining parts are concatenated).
     22 
     23 For example, if you have the array $[1, 3, 2]$, you can choose $i = 1$ (since $a_1 = 1 \lt a_2 = 3$), then either remove $a_1$ which gives the new array $[3, 2]$, or remove $a_2$ which gives the new array $[1, 2]$.
     24 
     25 Is it possible to make the length of this array equal to $1$ with these operations?
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$)  — the number of test cases. The description of the test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$)  — the length of the array.
     32 
     33 The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq n$, $a_i$ are pairwise distinct) — elements of the array.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output on a single line the word "YES" if it is possible to reduce the array to a single element using the aforementioned operation, or "NO" if it is impossible to do so.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 3
     48 1 2 3
     49 4
     50 3 1 2 4
     51 3
     52 2 3 1
     53 6
     54 2 4 6 1 3 5
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 YES
     61 YES
     62 NO
     63 YES
     64 ```
     65 
     66 Note
     67 
     68 For the first two test cases and the fourth test case, we can operate as follow (the bolded elements are the pair chosen for that operation):
     69 
     70 $[\text{1}, \textbf{2}, \textbf{3}] \rightarrow [\textbf{1}, \textbf{2}] \rightarrow [\text{1}]$
     71 
     72 $[\text{3}, \textbf{1}, \textbf{2}, \text{4}] \rightarrow [\text{3}, \textbf{1}, \textbf{4}] \rightarrow [\textbf{3}, \textbf{4}] \rightarrow [\text{4}]$
     73 
     74 $[\textbf{2}, \textbf{4}, \text{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\text{4}, \text{1}, \textbf{3}, \textbf{5}] \rightarrow [\text{4}, \textbf{1}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{5}] \rightarrow [\text{4}]$