codeforces-scrape

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

2123C.md (2401B)


      1 Source: https://codeforces.com/problemset/problem/2123/C
      2 
      3 C. Prefix Min and Suffix Max
      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 an array $a$ of distinct integers.
     22 
     23 In one operation, you may either:
     24 
     25 * choose a nonempty prefix$^{\text{∗}}$ of $a$ and replace it with its minimum value, or
     26 * choose a nonempty suffix$^{\text{†}}$ of $a$ and replace it with its maximum value.
     27 
     28 Note that you may choose the entire array $a$.
     29 
     30 For each element $a_i$, determine if there exists some sequence of operations to transform $a$ into $[a_i]$; that is, make the array $a$ consist of only one element, which is $a_i$. Output your answer as a binary string of length $n$, where the $i$-th character is $1$ if there exists a sequence to transform $a$ into $[a_i]$, and $0$ otherwise.
     31 
     32 $^{\text{∗}}$A prefix of an array is a subarray consisting of the first $k$ elements of the array, for some integer $k$.
     33 
     34 $^{\text{†}}$A suffix of an array is a subarray consisting of the last $k$ elements of the array, for some integer $k$.
     35 
     36 Input
     37 
     38 The first line contains an integer $t$ ($1 \leq t \leq 10^4$)  — the number of test cases.
     39 
     40 The first line of each test case contains one integer $n$ ($2 \leq n \leq 2\cdot 10^5$) — the size of the array $a$.
     41 
     42 The second line of each test case contains $n$ integers, $a_1,a_2,\dots,a_n$ ($1 \leq a_i \leq 10^6$). It is guaranteed that all $a_i$ are distinct.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case, output a binary string of length $n$  — the $i$-th character should be $1$ if there exists a sequence of operations as described above, and $0$ otherwise.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 3
     56 
     57 6
     58 
     59 1 3 5 4 7 2
     60 
     61 4
     62 
     63 13 10 12 20
     64 
     65 7
     66 
     67 1 2 3 4 5 6 7
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 100011
     74 1101
     75 1000001
     76 ```
     77 
     78 Note
     79 
     80 In the first sample, you can first choose the prefix of size $3$. Then the array is transformed into
     81 
     82 |  |  |  |  |
     83 | --- | --- | --- | --- |
     84 | 1 | 4 | 7 | 2 |
     85 
     86 Next, you can choose the suffix of size $2$. Then the array is transformed into
     87 
     88 |  |  |  |
     89 | --- | --- | --- |
     90 | 1 | 4 | 7 |
     91 
     92 Finally, you can choose the prefix of size $3$. Then the array is transformed into
     93 
     94 |  |
     95 | --- |
     96 | 1 |
     97 
     98 So we see that it is possible to transform $a$ into $[1]$.
     99 
    100 It can be shown that it is impossible to transform $a$ into $[3]$.