codeforces-scrape

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

1832C.md (1427B)


      1 Source: https://codeforces.com/problemset/problem/1832/C
      2 
      3 C. Contrast Value
      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 For an array of integers $[a_1, a_2, \dots, a_n]$, let's call the value $|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$ the contrast of the array. Note that the contrast of an array of size $1$ is equal to $0$.
     22 
     23 You are given an array of integers $a$. Your task is to build an array of $b$ in such a way that all the following conditions are met:
     24 
     25 * $b$ is not empty, i.e there is at least one element;
     26 * $b$ is a subsequence of $a$, i.e $b$ can be produced by deleting some elements from $a$ (maybe zero);
     27 * the contrast of $b$ is equal to the contrast of $a$.
     28 
     29 What is the minimum possible size of the array $b$?
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the size of the array $a$.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \cdot, a_n$ ($0 \le a_i \le 10^9$) — elements of the array itself.
     38 
     39 The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print a single integer — the minimum possible size of the array $b$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 5
     53 
     54 1 3 3 3 7
     55 
     56 2
     57 
     58 4 2
     59 
     60 4
     61 
     62 1 1 1 1
     63 
     64 7
     65 
     66 5 4 2 1 0 0 4
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2
     73 2
     74 1
     75 3
     76 ```