codeforces-scrape

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

2144B.md (2069B)


      1 Source: https://codeforces.com/problemset/problem/2144/B
      2 
      3 B. Maximum Cost Permutation
      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 Recall that a permutation of length $n$ is a sequence of length $n$ such that each integer from $1$ to $n$ appears in it exactly once.
     22 
     23 Let's define the cost of a permutation as the minimum length of its contiguous subsegment (possibly empty) that needs to be sorted so that the entire permutation becomes sorted in ascending order.
     24 
     25 You are given an integer array $p$ consisting of integers from $0$ to $n$, where no positive (strictly greater than zero) integer appears more than once. You should replace zeros with integers so that the array $p$ becomes a permutation.
     26 
     27 Your task is to calculate the maximum possible cost of the resulting permutation.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     34 
     35 The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le n$). No positive integer appears more than once in this sequence.
     36 
     37 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the maximum possible cost of the resulting permutation.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 5
     51 
     52 1 0 4 0 5
     53 
     54 3
     55 
     56 0 0 0
     57 
     58 4
     59 
     60 1 2 3 0
     61 
     62 3
     63 
     64 0 3 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 3
     71 
     72 3
     73 
     74 0
     75 
     76 2
     77 ```
     78 
     79 Note
     80 
     81 In the first example, you can make a permutation $[1, 3, 4, 2, 5]$ with the cost $3$, because you have to sort segment $[2, 4]$.
     82 
     83 In the second example, you can make a permutation $[2, 3, 1]$ with the cost $3$, because you have to sort segment $[1, 3]$.
     84 
     85 In the third example, there is only one possible permutation — $[1, 2, 3, 4]$, with the cost $0$, because the permutation is already sorted.
     86 
     87 In the fourth example, there is only one possible permutation — $[1, 3, 2]$, with the cost $2$, because you have to sort segment $[2, 3]$.