Discrete Centrifugal Jumps (Codeforces 1407D)
Tags: DP, graphs

There are $$$n$$$ beautiful skyscrapers in New York, the height of the $$$i$$$-th one is $$$h_i$$$. Today some villains have set on fire first $$$n - 1$$$ of them, and now the only safety building is $$$n$$$-th skyscraper.Let's call a jump from $$$i$$$-th skyscraper to $$$j$$$-th ($$$i < j$$$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $$$i < j$$$ and one of the following conditions satisfied:   $$$i + 1 = j$$$  $$$\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$$$  $$$\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$$$. At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach $$$n$$$-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.

Input: The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — total amount of skyscrapers.The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — heights of skyscrapers.

Output: Print single number $$$k$$$ — minimal amount of discrete jumps. We can show that an answer always exists.

Note: In the first testcase, Vasya can jump in the following way: $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$$$.In the second and third testcases, we can reach last skyscraper in one jump.Sequence of jumps in the fourth testcase: $$$1 \rightarrow 3 \rightarrow 5$$$.

Sample Inputs:
5
1 3 1 4 5

4
4 2 2 4

2
1 1

5
100 1 100 1 100

Sample Outputs:
3

1

1

2

Solution (Python):
def I1():
    n = int(input())
    h = [int(j) for j in input().split()]
    x = [0] * n
    y = [0]
    z = [0]
    for i in range(1, n):
        x[i] = x[i - 1] + 1
        while len(y) and h[i] >= h[y[-1]]:
            a = y[-1]
            y.pop()
            if h[i] > h[a] and len(y):
                x[i] = min(x[i], x[y[-1]] + 1)
        while len(z) and h[i] <= h[z[-1]]:
            a = z[-1]
            z.pop()
            if h[i] < h[a] and len(z):
                x[i] = min(x[i], x[z[-1]] + 1)
        y.append(i)
        z.append(i)
    print(x[-1])
if __name__ == '__main__':
    I1()

Solution (Python):
from collections import deque
from itertools import chain

def construct_links(h_and_idx):
    lt_stack = []
    gt_stack = []
    g = [[] for _ in h_and_idx]
    for (h, idx) in reversed(h_and_idx):
        prev_h = None
        while lt_stack and lt_stack[-1][0] >= h:
            (prev_h, prev_idx) = lt_stack.pop()
            g[idx].append(prev_idx)
        if lt_stack and prev_h != h:
            g[idx].append(lt_stack[-1][1])
        lt_stack.append((h, idx))
        prev_h = None
        while gt_stack and gt_stack[-1][0] <= h:
            (prev_h, prev_idx) = gt_stack.pop()
            g[idx].append(prev_idx)
        if gt_stack and prev_h != h:
            g[idx].append(gt_stack[-1][1])
        gt_stack.append((h, idx))
    return g

def main():
    n = int(input())
    h_and_idx = tuple(((h, i) for (i, h) in enumerate(map(int, input().split()))))
    g = construct_links(h_and_idx)
    dist = [0] + [-1] * (n - 1)
    q = deque([0], n)
    while q:
        v = q.popleft()
        for x in g[v]:
            if dist[x] == -1:
                dist[x] = dist[v] + 1
                q.append(x)
    print(dist[-1])
if __name__ == '__main__':
    main()

Solution (Python):
import operator as ops
from collections import deque
from itertools import chain

def construct_links(h_and_idx):
    lt_stack = []
    gt_stack = []
    g = [[] for _ in h_and_idx]
    for (h, idx) in reversed(h_and_idx):
        for (stack, cmp_op) in [(lt_stack, ops.le), (gt_stack, ops.ge)]:
            prev_h = None
            while stack and cmp_op(h, stack[-1][0]):
                (prev_h, prev_idx) = stack.pop()
                g[idx].append(prev_idx)
            if stack and prev_h != h:
                g[idx].append(stack[-1][1])
            stack.append((h, idx))
    return g

def main():
    n = int(input())
    h_and_idx = tuple(((h, i) for (i, h) in enumerate(map(int, input().split()))))
    g = construct_links(h_and_idx)
    dist = [0] + [-1] * (n - 1)
    q = deque([0], n)
    while q:
        v = q.popleft()
        for x in g[v]:
            if dist[x] == -1:
                dist[x] = dist[v] + 1
                q.append(x)
    print(dist[-1])
if __name__ == '__main__':
    main()