Range and Partition (Codeforces 1630B)
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):
import bisect
import collections
import math
import random
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 binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def solve():
    (n, k) = LI()
    a = LI()
    b = a.copy()
    b.sort()
    minrangedif = 10 ** 9
    r = [a[0], a[-1]]
    for i in range(n // 2 - k // 2 + 2):
        if i + (n + k + 1) // 2 - 1 < n and b[i + (n + k + 1) // 2 - 1] - b[i] < minrangedif:
            minrangedif = b[i + (n + k + 1) // 2 - 1] - b[i]
            r = [b[i], b[i + (n + k + 1) // 2 - 1]]
    inside = out = 0
    begin = 1
    ans = [str(r[0]) + ' ' + str(r[1])]
    for i in range(n):
        if inside == out and (r[0] <= a[i] and a[i] <= r[1]):
            inside = out = 0
            ans.append(str(begin) + ' ' + str(i + 1))
            begin = i + 2
            k -= 1
            if k == 0:
                break
        elif r[0] <= a[i] and a[i] <= r[1]:
            inside += 1
        else:
            out += 1
    z = ans.pop().split(' ')
    ans.append(z[0] + ' ' + str(n))
    return '\n'.join(ans)

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

Solution (Python):
import bisect
import collections
import math
import random
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 binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def solve():
    (n, k) = li()
    a = li()
    b = a.copy()
    b.sort()
    minrangedif = 10 ** 9
    r = [a[0], a[-1]]
    for i in range(n // 2 - k // 2 + 2):
        if i + (n + k + 1) // 2 - 1 < n and b[i + (n + k + 1) // 2 - 1] - b[i] < minrangedif:
            minrangedif = b[i + (n + k + 1) // 2 - 1] - b[i]
            r = [b[i], b[i + (n + k + 1) // 2 - 1]]
    inside = out = 0
    begin = 1
    ans = [str(r[0]) + ' ' + str(r[1])]
    for i in range(n):
        if inside == out and (r[0] <= a[i] and a[i] <= r[1]):
            inside = out = 0
            ans.append(str(begin) + ' ' + str(i + 1))
            begin = i + 2
            k -= 1
            if k == 0:
                break
        elif r[0] <= a[i] and a[i] <= r[1]:
            inside += 1
        else:
            out += 1
    z = ans.pop().split(' ')
    ans.append(z[0] + ' ' + str(n))
    return '\n'.join(ans)

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

Solution (Python):
for _ in range(int(input())):
    (n, k) = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = a[:]
    b.sort()
    needed = (n + k + 1) // 2 - 1
    (md, ml, mr) = (b[needed] - b[0], 0, needed)
    for i in range(needed, n):
        cd = b[i] - b[i - needed]
        if cd < md:
            (md, ml, mr) = (cd, i - needed, i)
    print(b[ml], b[mr])
    balance = 0
    splits = []
    for i in range(n):
        if len(splits) >= k - 1:
            break
        if b[ml] <= a[i] <= b[mr]:
            balance += 1
        else:
            balance -= 1
        if balance > 0:
            balance = 0
            splits.append(i)
    if k > 1:
        print(1, splits[0] + 1)
        for i in range(1, k - 1):
            print(splits[i - 1] + 2, splits[i] + 1)
        print(splits[-1] + 2, n)
    else:
        print(1, n)