codeforces-scrape

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

1919C.md (2273B)


      1 Source: https://codeforces.com/problemset/problem/1919/C
      2 
      3 C. Grouping Increases
      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 You are given an array $a$ of size $n$. You will do the following process to calculate your penalty:
     22 
     23 1. Split array $a$ into two (possibly empty) subsequences$^\dagger$ $s$ and $t$ such that every element of $a$ is either in $s$ or $t^\ddagger$.
     24 2. For an array $b$ of size $m$, define the penalty $p(b)$ of an array $b$ as the number of indices $i$ between $1$ and $m - 1$ where $b_i \lt b_{i + 1}$.
     25 3. The total penalty you will receive is $p(s) + p(t)$.
     26 
     27 If you perform the above process optimally, find the minimum possible penalty you will receive.
     28 
     29 $^\dagger$ A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) elements.
     30 
     31 $^\ddagger$ Some valid ways to split array $a=[3,1,4,1,5]$ into $(s,t)$ are $([3,4,1,5],[1])$, $([1,1],[3,4,5])$ and $([\,],[3,1,4,1,5])$ while some invalid ways to split $a$ are $([3,4,5],[1])$, $([3,1,4,1],[1,5])$ and $([1,3,4],[5,1])$.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.
     36 
     37 The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the size of the array $a$.
     38 
     39 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the array $a$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output a single integer representing the minimum possible penalty you will receive.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 5
     55 
     56 1 2 3 4 5
     57 
     58 8
     59 
     60 8 2 3 1 1 7 4 3
     61 
     62 5
     63 
     64 3 3 3 3 3
     65 
     66 1
     67 
     68 1
     69 
     70 2
     71 
     72 2 1
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 3
     79 1
     80 0
     81 0
     82 0
     83 ```
     84 
     85 Note
     86 
     87 In the first test case, a possible way to split $a$ is $s=[2,4,5]$ and $t=[1,3]$. The penalty is $p(s)+p(t)=2 + 1 =3$.
     88 
     89 In the second test case, a possible way to split $a$ is $s=[8,3,1]$ and $t=[2,1,7,4,3]$. The penalty is $p(s)+p(t)=0 + 1 =1$.
     90 
     91 In the third test case, a possible way to split $a$ is $s=[\,]$ and $t=[3,3,3,3,3]$. The penalty is $p(s)+p(t)=0 + 0 =0$.