codeforces-scrape

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

1674D.md (2611B)


      1 Source: https://codeforces.com/problemset/problem/1674/D
      2 
      3 D. A-B-C Sort
      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 three arrays $a$, $b$ and $c$. Initially, array $a$ consists of $n$ elements, arrays $b$ and $c$ are empty.
     22 
     23 You are performing the following algorithm that consists of two steps:
     24 
     25 * Step $1$: while $a$ is not empty, you take the last element from $a$ and move it in the middle of array $b$. If $b$ currently has odd length, you can choose: place the element from $a$ to the left or to the right of the middle element of $b$. As a result, $a$ becomes empty and $b$ consists of $n$ elements.
     26 * Step $2$: while $b$ is not empty, you take the middle element from $b$ and move it to the end of array $c$. If $b$ currently has even length, you can choose which of two middle elements to take. As a result, $b$ becomes empty and $c$ now consists of $n$ elements.
     27 
     28 Refer to the Note section for examples.
     29 
     30 Can you make array $c$ sorted in non-decreasing order?
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Next $t$ cases follow.
     35 
     36 The first line of each test case contains the single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of array $a$.
     37 
     38 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$ itself.
     39 
     40 It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test, print YES (case-insensitive), if you can make array $c$ sorted in non-decreasing order. Otherwise, print NO (case-insensitive).
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 3
     52 
     53 4
     54 
     55 3 1 5 3
     56 
     57 3
     58 
     59 3 2 1
     60 
     61 1
     62 
     63 7331
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 YES
     70 NO
     71 YES
     72 ```
     73 
     74 Note
     75 
     76 In the first test case, we can do the following for $a = [3, 1, 5, 3]$:
     77 
     78 Step $1$:
     79 
     80 |  |  |  |  |  |  |  |  |  |  |
     81 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     82 | $a$ | $[3, 1, 5, 3]$ | $\Rightarrow$ | $[3, 1, 5]$ | $\Rightarrow$ | $[3, 1]$ | $\Rightarrow$ | $[3]$ | $\Rightarrow$ | $[]$ |
     83 | $b$ | $[]$ |  | $[\underline{3}]$ |  | $[3, \underline{5}]$ |  | $[3, \underline{1}, 5]$ |  | $[3, \underline{3}, 1, 5]$ |
     84 
     85 Step $2$:
     86 
     87 |  |  |  |  |  |  |  |  |  |  |
     88 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     89 | $b$ | $[3, 3, \underline{1}, 5]$ | $\Rightarrow$ | $[3, \underline{3}, 5]$ | $\Rightarrow$ | $[\underline{3}, 5]$ | $\Rightarrow$ | $[\underline{5}]$ | $\Rightarrow$ | $[]$ |
     90 | $c$ | $[]$ |  | $[1]$ |  | $[1, 3]$ |  | $[1, 3, 3]$ |  | $[1, 3, 3, 5]$ |
     91 
     92 As a result, array $c = [1, 3, 3, 5]$ and it's sorted.