codeforces-scrape

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

1819A.md (2712B)


      1 Source: https://codeforces.com/problemset/problem/1819/A
      2 
      3 A. Constructive Problem
      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 As you know, any problem that does not require the use of complex data structures is considered constructive. You are offered to solve one of such problems.
     22 
     23 You are given an array $a$ of $n$ non-negative integers. You are allowed to perform the following operation exactly once: choose some non-empty subsegment $a_l, a_{l+1}, \ldots, a_r$ of the array $a$ and a non-negative integer $k$, and assign value $k$ to all elements of the array on the chosen subsegment.
     24 
     25 The task is to find out whether $\operatorname{MEX}(a)$ can be increased by exactly one by performing such an operation. In other words, if before the operation $\operatorname{MEX}(a) = m$ held, then after the operation it must hold that $\operatorname{MEX}(a) = m + 1$.
     26 
     27 Recall that $\operatorname{MEX}$ of a set of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the set $c$.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50\,000$) — the number of test cases. The description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of elements of array $a$.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — elements of array $a$.
     36 
     37 It is guaranteed that the sum $n$ over all test cases does not exceed $200\,000$.
     38 
     39 Output
     40 
     41 For each test case, print "Yes" if you can increase $\operatorname{MEX}(a)$ by exactly one by performing the operation from the statement exactly once, otherwise print "No".
     42 
     43 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 3
     53 
     54 1 2 1
     55 
     56 4
     57 
     58 0 2 2 0
     59 
     60 4
     61 
     62 3 2 0 2
     63 
     64 1
     65 
     66 0
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 Yes
     73 Yes
     74 No
     75 No
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, $\operatorname{MEX}(a) = 0$. If you set all elements of $a$ to $0$, then $\operatorname{MEX}$ of the resulting array will be $1$, and thus will increase by one.
     81 
     82 In the second test case, $\operatorname{MEX}(a) = 1$. If we assign a value of $1$ to the elements of $a$ on a subsegment from $2$ to $3$, we get an array $[0, 1, 1, 0]$ for which $\operatorname{MEX}$ is $2$, and thus is increased by one compared to the original.
     83 
     84 It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of $\operatorname{MEX}(a)$ increases by exactly one.