codeforces-scrape

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

1054B.md (3078B)


      1 Source: https://codeforces.com/problemset/problem/1054/B
      2 
      3 B. Appending Mex
      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 Initially Ildar has an empty array. He performs $n$ steps. On each step he takes a subset of integers already added to the array and appends the mex of this subset to the array.
     22 
     23 The mex of an multiset of integers is the smallest non-negative integer not presented in the multiset. For example, the mex of the multiset $[0, 2, 3]$ is $1$, while the mex of the multiset $[1, 2, 1]$ is $0$.
     24 
     25 More formally, on the step $m$, when Ildar already has an array $a_1, a_2, \ldots, a_{m-1}$, he chooses some subset of indices $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \lt m$ (possibly, empty), where $0 \leq k \lt m$, and appends the $mex(a_{i_1}, a_{i_2}, \ldots a_{i_k})$ to the end of the array.
     26 
     27 After performing all the steps Ildar thinks that he might have made a mistake somewhere. He asks you to determine for a given array $a_1, a_2, \ldots, a_n$ the minimum step $t$ such that he has definitely made a mistake on at least one of the steps $1, 2, \ldots, t$, or determine that he could have obtained this array without mistakes.
     28 
     29 Input
     30 
     31 The first line contains a single integer $n$ ($1 \leq n \leq 100\,000$) — the number of steps Ildar made.
     32 
     33 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array Ildar obtained.
     34 
     35 Output
     36 
     37 If Ildar could have chosen the subsets on each step in such a way that the resulting array is $a_1, a_2, \ldots, a_n$, print $-1$.
     38 
     39 Otherwise print a single integer $t$ — the smallest index of a step such that a mistake was made on at least one step among steps $1, 2, \ldots, t$.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4  
     47 0 1 2 1
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 -1
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 3  
     60 1 0 1
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 4  
     73 0 1 2 239
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 4
     80 ```
     81 
     82 Note
     83 
     84 In the first example it is possible that Ildar made no mistakes. Here is the process he could have followed.
     85 
     86 * $1$-st step. The initial array is empty. He can choose an empty subset and obtain $0$, because the mex of an empty set is $0$. Appending this value to the end he gets the array $[0]$.
     87 * $2$-nd step. The current array is $[0]$. He can choose a subset $[0]$ and obtain an integer $1$, because $mex(0) = 1$. Appending this value to the end he gets the array $[0,1]$.
     88 * $3$-rd step. The current array is $[0,1]$. He can choose a subset $[0,1]$ and obtain an integer $2$, because $mex(0,1) = 2$. Appending this value to the end he gets the array $[0,1,2]$.
     89 * $4$-th step. The current array is $[0,1,2]$. He can choose a subset $[0]$ and obtain an integer $1$, because $mex(0) = 1$. Appending this value to the end he gets the array $[0,1,2,1]$.
     90 
     91 Thus, he can get the array without mistakes, so the answer is $-1$.
     92 
     93 In the second example he has definitely made a mistake on the very first step, because he could not have obtained anything different from $0$.
     94 
     95 In the third example he could have obtained $[0, 1, 2]$ without mistakes, but $239$ is definitely wrong.