Range and Partition (Codeforces 1631D)
Tags: Greedy, two pointers

Given an array $$$a$$$ of $$$n$$$ integers, find a range of values $$$[x, y]$$$ ($$$x \le y$$$), and split $$$a$$$ into exactly $$$k$$$ ($$$1 \le k \le n$$$) subarrays in such a way that:  Each subarray is formed by several continuous elements of $$$a$$$, that is, it is equal to $$$a_l, a_{l+1}, \ldots, a_r$$$ for some $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).  Each element from $$$a$$$ belongs to exactly one subarray.  In each subarray the number of elements inside the range $$$[x, y]$$$ (inclusive) is strictly greater than the number of elements outside the range. An element with index $$$i$$$ is inside the range $$$[x, y]$$$ if and only if $$$x \le a_i \le y$$$.  Print any solution that minimizes $$$y - x$$$.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$ and the number of subarrays required in the partition.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) where $$$a_i$$$ is the $$$i$$$-th element of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, print $$$k+1$$$ lines.In the first line, print $$$x$$$ and $$$y$$$ — the limits of the found range.Then print $$$k$$$ lines, the $$$i$$$-th should contain $$$l_i$$$ and $$$r_i$$$ ($$$1\leq l_i \leq r_i \leq n$$$) — the limits of the $$$i$$$-th subarray.You can print the subarrays in any order.

Note: In the first test, there should be only one subarray, which must be equal to the whole array. There are $$$2$$$ elements inside the range $$$[1, 2]$$$ and $$$0$$$ elements outside, if the chosen range is $$$[1, 1]$$$, there will be $$$1$$$ element inside ($$$a_1$$$) and $$$1$$$ element outside ($$$a_2$$$), and the answer will be invalid.In the second test, it is possible to choose the range $$$[2, 2]$$$, and split the array in subarrays $$$(1, 3)$$$ and $$$(4, 4)$$$, in subarray $$$(1, 3)$$$ there are $$$2$$$ elements inside the range ($$$a_2$$$ and $$$a_3$$$) and $$$1$$$ element outside ($$$a_1$$$), in subarray $$$(4, 4)$$$ there is only $$$1$$$ element ($$$a_4$$$), and it is inside the range.In the third test, it is possible to choose the range $$$[5, 5]$$$, and split the array in subarrays $$$(1, 4)$$$, $$$(5, 7)$$$ and $$$(8, 11)$$$, in the subarray $$$(1, 4)$$$ there are $$$3$$$ elements inside the range and $$$1$$$ element outside, in the subarray $$$(5, 7)$$$ there are $$$2$$$ elements inside and $$$1$$$ element outside and in the subarray $$$(8, 11)$$$ there are $$$3$$$ elements inside and $$$1$$$ element outside.

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

Sample Outputs:
1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11

Solution (Python):
from sys import stdin, gettrace
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def solve(n, k, aa):
    bb = sorted(aa)
    xy = zip(bb, bb[(n + k + 1) // 2 - 1:])
    (x, y) = min(xy, key=lambda v: v[1] - v[0])
    lr = []
    l = 1
    cnt = 0
    for (i, a) in enumerate(aa, 1):
        if x <= a <= y:
            cnt += 1
        else:
            cnt -= 1
        if cnt == 1:
            lr.append([l, i])
            cnt = 0
            l = i + 1
    lr.append([l, n])
    lr = lr[:k]
    lr[-1][1] = n
    return (x, y, lr)

def main():
    t = int(input())
    for _ in range(t):
        (n, k) = map(int, input().split())
        aa = [int(a) for a in input().split()]
        (x, y, lr) = solve(n, k, aa)
        print(x, y)
        for (l, r) in lr:
            print(l, r)
if __name__ == '__main__':
    main()

Solution (Python):
import math

def solve(a, n, k):
    m = math.ceil((n + k) / 2)
    cnt = [0] * (n + 1)
    for aa in a:
        cnt[aa] += 1
    min_len = n + 111
    (l, r) = (0, 0)
    (i, j) = (1, 1)
    num = 0
    while j <= n + 1:
        if num < m:
            if j == n + 1:
                break
            num += cnt[j]
            j += 1
        else:
            if j - i < min_len:
                min_len = j - i
                l = i
                r = j - 1
            num -= cnt[i]
            i += 1
    print(l, r)
    begin = 0
    for i in range(k - 1):
        num = 0
        for j in range(begin, n):
            if l <= a[j] <= r:
                num += 1
            else:
                num -= 1
            if num >= 1:
                print(begin + 1, j + 1)
                begin = j + 1
                break
    print(begin + 1, n)
    return
t = int(input())
while t:
    (n, k) = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    solve(a, n, k)
    t -= 1

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    sa = sorted(a)
    cnt = [0 for i in range(n + 1)]
    for i in range(n):
        cnt[a[i]] += 1
    for i in range(2, n + 1):
        cnt[i] += cnt[i - 1]
    ans = (-1, n)
    need = (n + k + 1) // 2
    for i in range(n - need + 1):
        new_ans = (sa[i], sa[i + need - 1])
        if new_ans[1] - new_ans[0] < ans[1] - ans[0]:
            ans = new_ans
    print(ans[0], ans[1])
    lst = 0
    cnt = 0
    for i in range(n):
        if k == 1:
            break
        if ans[0] <= a[i] <= ans[1]:
            cnt += 1
        else:
            cnt -= 1
        if cnt > 0:
            print(lst + 1, i + 1)
            lst = i + 1
            cnt = 0
            k -= 1
    print(lst + 1, n)