codeforces-scrape

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

2171D.md (2674B)


      1 Source: https://codeforces.com/problemset/problem/2171/D
      2 
      3 D. Rae Taylor and Trees (easy version)
      4 
      5 time limit per test
      6 
      7 3 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 "To think a commoner would even fathom sitting next to me. Know your place!"
     22 
     23 — Claire François
     24 
     25 This is the easy version of the problem. The only difference between the easy and hard versions is that the hard version asks you to construct an example of a satisfactory tree.
     26 
     27 As an Earth mage, Rae has mastered the spell of growing trees! But Manaria brags that she can grow a more impressive species of trees. Rae remembers that the most rare type of tree can be grown using a formula represented by a certain permutation — please help her construct it!
     28 
     29 You are given a permutation$^{\text{∗}}$ $p$ of length $n$.
     30 
     31 Determine if there exists an undirected tree with $n$ vertices labeled $1, 2, \dots, n$, satisfying the following condition:
     32 
     33 * Let $u$ and $v$ ($1\leq {\color{red}{u \lt v}} \leq n$) be any two vertices connected by an edge. Then $u$ appears before $v$ in $p$.
     34 
     35 $^{\text{∗}}$A permutation of length $n$ is an array that contains every integer from $1$ to $n$ exactly once, in any order.
     36 
     37 Input
     38 
     39 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$)  — the number of test cases.
     40 
     41 The first line of each test case contains a single integer $n$ ($2\leq n\leq 2\cdot 10^5$).
     42 
     43 The second line of each test case contains $n$ integers, $p_1, p_2, \dots, p_n$ ($1\leq p_i\leq n$). It is guaranteed that all $p_i$ are distinct.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, output on a single line "Yes" if there exists a tree satisfying the given condition, and "No" otherwise.
     50 
     51 You may output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "YES", and "yeS" will be recognized as "Yes".
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 9
     59 
     60 6
     61 
     62 1 3 4 5 2 6
     63 
     64 4
     65 
     66 3 4 1 2
     67 
     68 5
     69 
     70 4 3 5 1 2
     71 
     72 4
     73 
     74 1 2 3 4
     75 
     76 7
     77 
     78 4 3 5 7 6 2 1
     79 
     80 6
     81 
     82 2 4 6 1 3 5
     83 
     84 3
     85 
     86 2 1 3
     87 
     88 4
     89 
     90 2 4 1 3
     91 
     92 6
     93 
     94 4 2 6 5 1 3
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 Yes
    101 
    102 No
    103 
    104 No
    105 
    106 Yes
    107 
    108 No
    109 
    110 Yes
    111 
    112 Yes
    113 
    114 Yes
    115 
    116 Yes
    117 ```
    118 
    119 Note
    120 
    121 In the first example, we can construct the tree with the following edges:
    122 
    123 * $\{3, 1\}$,
    124 * $\{4, 1\}$,
    125 * $\{6, 5\}$,
    126 * $\{6, 2\}$,
    127 * $\{6, 1\}$.
    128 
    129 Then we have that
    130 
    131 * $1 \lt 3$, and $1$ appears before $3$ in $p$,
    132 * $1 \lt 4$, and $1$ appears before $4$ in $p$,
    133 * $5 \lt 6$, and $5$ appears before $6$ in $p$,
    134 * $2 \lt 6$, and $2$ appears before $6$ in $p$,
    135 * $1 \lt 6$, and $1$ appears before $6$ in $p$.
    136 
    137 In the second example, it can be shown that there does not exist a tree satisfying the given constraints.