Contrast Value (Codeforces 1832C)
Tags: Greedy, implementation

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$$$.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:  $$$b$$$ is not empty, i.e there is at least one element;  $$$b$$$ is a subsequence of $$$a$$$, i.e $$$b$$$ can be produced by deleting some elements from $$$a$$$ (maybe zero);  the contrast of $$$b$$$ is equal to the contrast of $$$a$$$. What is the minimum possible size of the array $$$b$$$?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.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$$$.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.The sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print a single integer — the minimum possible size of the array $$$b$$$.


Sample Inputs:
4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4

Sample Outputs:
2
2
1
3

Solution (Python):
def Minimum_length(array, N):
    count = 1
    parity = 0
    for i in range(N - 1):
        if array[i] < array[i + 1] and parity != 1:
            count += 1
            parity = 1
        elif array[i] > array[i + 1] and parity != -1:
            count += 1
            parity = -1
    print(count)
    return
t = int(input())
while t:
    N = int(input())
    array = [int(j) for j in input().split(' ')]
    Minimum_length(array, N)
    t -= 1

Solution (Python):
import bisect
import collections
import heapq
import math
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)

def solve():
    n = ii()
    a = li()
    if a.count(a[0]) == n:
        return 1
    for j in range(n - 1):
        if a[j] != a[j + 1]:
            inc = a[j] < a[j + 1]
            dec = a[j] > a[j + 1]
            break
    ans = 2
    for i in range(j + 1, n - 1):
        if inc:
            if a[i] > a[i + 1]:
                inc = False
                dec = True
                ans += 1
        elif dec:
            if a[i] < a[i + 1]:
                dec = False
                inc = True
                ans += 1
    return ans

def main():
    for _ in range(ii()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from re import search
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : int(sys.stdin.readline().rstrip('\r\n'))
mi = lambda x=int: map(x, sys.stdin.readline().rstrip('\r\n').split())
li = lambda x=int: list(mi(x))
lb = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n')))
ls = lambda : list(sys.stdin.readline().rstrip('\r\n'))
bi = lambda n: bin(n).replace('0b', '')
sbstr = lambda a, s: search(a, s)

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
yn = ['No', 'Yes']
YN = ['NO', 'YES']
YY = 'YES'
NN = 'NO'
yy = 'Yes'
nn = 'No'
inf = sys.maxsize
mod = 998244353
alp = 'abcdefghijklmnopqrstuvwxyz'
from itertools import accumulate as cml
from collections import Counter as ctr, deque as dq, defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from math import ceil, gcd, log, sqrt
import heapq as hq

def main(kase):
    n = inp()
    a = li()
    p = a[0]
    c = 0
    for i in range(1, n - 1):
        if p <= a[i] <= a[i + 1] or p >= a[i] >= a[i + 1]:
            c += 1
        else:
            p = a[i]
    if c == n - 2:
        if a[0] == a[-1]:
            print(1)
        else:
            print(2)
        return
    print(n - c)
    pass
if __name__ == '__main__':
    test_Cases = 1
    test_Cases = inp()
    for i in range(test_Cases):
        main(i)