Avoid Local Maximums (Codeforces 1635B)
Tags: Greedy, greedy

You are given an array $$$a$$$ of size $$$n$$$. Each element in this array is an integer between $$$1$$$ and $$$10^9$$$.You can perform several operations to this array. During an operation, you can replace an element in the array with any integer between $$$1$$$ and $$$10^9$$$. Output the minimum number of operations needed such that the resulting array doesn't contain any local maximums, and the resulting array after the operations.An element $$$a_i$$$ is a local maximum if it is strictly larger than both of its neighbors (that is, $$$a_i > a_{i - 1}$$$ and $$$a_i > a_{i + 1}$$$). Since $$$a_1$$$ and $$$a_n$$$ have only one neighbor each, they will never be a local maximum.

Input: Each test contains multiple test cases. The first line will contain a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ — the size of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots ,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$, the elements of array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, first output a line containing a single integer $$$m$$$ — minimum number of operations required. Then ouput a line consist of $$$n$$$ integers — the resulting array after the operations. Note that this array should differ in exactly $$$m$$$ elements from the initial array.If there are multiple answers, print any.

Note: In the first example, the array contains no local maximum, so we don't need to perform operations.In the second example, we can change $$$a_2$$$ to $$$3$$$, then the array don't have local maximums.

Sample Inputs:
5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3

Sample Outputs:
0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3

Solution (Python):
from enum import Enum, auto
import copy
import sys
import math
input = sys.stdin.readline

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        res = 0
        copy_a = copy.copy(a)
        prev_1 = a[1]
        prev_2 = a[0]
        for (i, ai) in enumerate(a):
            if i == 0 or i == 1:
                continue
            if prev_2 < prev_1 and prev_1 > ai:
                res += 1
                if i + 1 < n and ai < a[i + 1] and (a[i + 1] > prev_1):
                    copy_a[i] = a[i + 1]
                    prev_2 = prev_1
                    prev_1 = a[i + 1]
                else:
                    copy_a[i] = prev_1
                    prev_2 = prev_1
            else:
                prev_2 = prev_1
                prev_1 = ai
        print(res)
        print(' '.join(map(str, copy_a)))
main()

Solution (Python):
def i():
    n = int(input())
    s = list(map(int, input().split()))
    c = 0
    for x in range(1, n - 2):
        if s[x] > s[x - 1] and s[x] > s[x + 1]:
            s[x + 1] = max(s[x], s[x + 2])
            c += 1
    if s[n - 2] > s[n - 3] and s[n - 2] > s[n - 1] and (n > 2):
        c += 1
        s[n - 1] = s[n - 2]
    return f"{c}\n{' '.join(map(str, s))}"
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
import sys
import math

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

def rs():
    return sys.stdin.readline().rstrip()

def ri():
    return int(sys.stdin.readline())

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

def ws(s):
    sys.stdout.write(s + '\n')

def wi(n):
    sys.stdout.write(str(n) + '\n')

def wia(a):
    sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def main(tc: int):
    n = ri()
    a = ria()
    cnt = 0
    for i in range(1, n - 1):
        if a[i] > a[i - 1] and a[i] > a[i + 1]:
            if i == n - 2:
                a[i + 1] = a[i]
            else:
                a[i + 1] = max(a[i], a[i + 2])
            cnt += 1
    wi(cnt)
    wia(a)
if __name__ == '__main__':
    t = ri()
    for tc in range(1, t + 1):
        main(tc)