Colorful Table (Codeforces 1870C)
Tags: Math, two pointers

You are given two integers $$$n$$$ and $$$k$$$. You are also given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of size $$$n$$$. It is known that for all $$$1 \leq i \leq n$$$, $$$1 \leq a_i \leq k$$$.Define a two-dimensional array $$$b$$$ of size $$$n \times n$$$ as follows: $$$b_{i, j} = \min(a_i, a_j)$$$. Represent array $$$b$$$ as a square, where the upper left cell is $$$b_{1, 1}$$$, rows are numbered from top to bottom from $$$1$$$ to $$$n$$$, and columns are numbered from left to right from $$$1$$$ to $$$n$$$. Let the color of a cell be the number written in it (for a cell with coordinates $$$(i, j)$$$, this is $$$b_{i, j}$$$).For each color from $$$1$$$ to $$$k$$$, find the smallest rectangle in the array $$$b$$$ containing all cells of this color. Output the sum of width and height of this rectangle.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follows the description of the test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$) — the size of array $$$a$$$ and the number of colors.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq k$$$) — the array $$$a$$$.It is guaranteed that the sum of the values of $$$n$$$ and $$$k$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output $$$k$$$ numbers: the sums of width and height of the smallest rectangle containing all cells of a color, for each color from $$$1$$$ to $$$k$$$.

Note: In the first test case, the entire array $$$b$$$ consists of color $$$1$$$, so the smallest rectangle for color $$$1$$$ has a size of $$$2 \times 2$$$, and the sum of its sides is $$$4$$$.In the second test case, the array $$$b$$$ looks like this:1112One of the corner cells has color $$$2$$$, and the other three cells have color $$$1$$$. Therefore, the smallest rectangle for color $$$1$$$ has a size of $$$2 \times 2$$$, and for color $$$2$$$ it is $$$1 \times 1$$$.In the last test case, the array $$$b$$$ looks like this:1111112221123211222111111

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

Sample Outputs:
4 
4 2 
0 6 6 2 0 
8 6 
10 6 2

Solution (Python):
def solve(n, k, lt):
    dic = {}
    StringAns = ''
    start = 0
    end = n - 1
    for ele in lt:
        dic[ele] = True
    for i in range(1, k + 1):
        if i not in dic:
            StringAns += '0 '
        else:
            while lt[start] < i:
                start += 1
            while lt[end] < i:
                end -= 1
            StringAns += str((end - start + 1) * 2) + ' '
    print(StringAns)
t = int(input())
for i in range(t):
    txt = input()
    (n, k) = list(map(int, txt.split(' ')))
    txt = input()
    lt = list(map(int, txt.split(' ')))
    solve(n, k, lt)

Solution (Python):
ans = []
for _ in range(int(input())):
    (n, k) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    (left, right) = (1, n)
    ns = []
    ns_clear = [0 for _ in range(k)]
    for i in range(1, k + 1):
        while a[left - 1] < i and left < right:
            left += 1
        while a[right - 1] < i and right > left:
            right -= 1
        ns.append(2 * (right - left + 1))
    for elem in a:
        ns_clear[elem - 1] = ns[elem - 1]
    ans.append(ns_clear)
for ns in ans:
    print(' '.join(map(str, ns)))

Solution (Python):
from sys import stdin
INF = float('inf')
input = lambda : stdin.readline().rstrip('\n')
t = int(input())

def solve():
    (n, k) = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    s = set(a)
    (l, r) = (0, n - 1)
    for i in range(1, k + 1):
        if not i in s:
            print(0, end=' ')
            continue
        while l <= r and (a[l] < i or a[r] < i):
            if a[l] < i:
                l += 1
            if a[r] < i:
                r -= 1
        print(2 * (r - l + 1), end=' ')
    print()
    return
for _ in range(t):
    solve()