Colors and Intervals (Codeforces 1552E)
Tags: Greedy, sortings

The numbers $$$1, \, 2, \, \dots, \, n \cdot k$$$ are colored with $$$n$$$ colors. These colors are indexed by $$$1, \, 2, \, \dots, \, n$$$. For each $$$1 \le i \le n$$$, there are exactly $$$k$$$ numbers colored with color $$$i$$$.Let $$$[a, \, b]$$$ denote the interval of integers between $$$a$$$ and $$$b$$$ inclusive, that is, the set $$$\{a, \, a + 1, \, \dots, \, b\}$$$. You must choose $$$n$$$ intervals $$$[a_1, \, b_1], \, [a_2, \, b_2], \, \dots, [a_n, \, b_n]$$$ such that:   for each $$$1 \le i \le n$$$, it holds $$$1 \le a_i < b_i \le n \cdot k$$$;  for each $$$1 \le i \le n$$$, the numbers $$$a_i$$$ and $$$b_i$$$ are colored with color $$$i$$$;  each number $$$1 \le x \le n \cdot k$$$ belongs to at most $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals. One can show that such a family of intervals always exists under the given constraints.

Input: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) — the number of colors and the number of occurrences of each color.The second line contains $$$n \cdot k$$$ integers $$$c_1, \, c_2, \, \dots, \, c_{nk}$$$ ($$$1 \le c_j \le n$$$), where $$$c_j$$$ is the color of number $$$j$$$. It is guaranteed that, for each $$$1 \le i \le n$$$, it holds $$$c_j = i$$$ for exactly $$$k$$$ distinct indices $$$j$$$.

Output: Output $$$n$$$ lines. The $$$i$$$-th line should contain the two integers $$$a_i$$$ and $$$b_i$$$.If there are multiple valid choices of the intervals, output any.

Note: In the first sample, each number can be contained in at most $$$\left\lceil \frac{4}{3 - 1} \right\rceil = 2$$$ intervals. The output is described by the following picture:  In the second sample, the only interval to be chosen is forced to be $$$[1, \, 2]$$$, and each number is indeed contained in at most $$$\left\lceil \frac{1}{2 - 1} \right\rceil = 1$$$ interval.In the third sample, each number can be contained in at most $$$\left\lceil \frac{3}{3 - 1} \right\rceil = 2$$$ intervals. The output is described by the following picture:  

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

1 2
1 1

3 3
3 1 2 3 2 1 2 1 3

2 3
2 1 1 1 2 2

Sample Outputs:
4 5
1 7
8 11
6 12

1 2

6 8
3 7
1 4

2 3
5 6

Solution (Python):
(n, k) = map(int, input().split(' '))
arr = [int(x) - 1 for x in input().split()]
m = 0 - -n // (k - 1)
gp = [[] for x in range(n)]
ct = 0
for x in arr:
    gp[x].append(ct)
    ct += 1
c = 1
L = [x for x in range(n)]
ans = [[] for x in range(n)]
while L:
    y = []
    for x in L:
        y.append([gp[x][c], x])
    y.sort(key=lambda x: x[0])
    for x in y[:m]:
        ans[x[1]].append(gp[x[1]][c - 1])
        ans[x[1]].append(x[0])
    L = []
    for x in y[m:]:
        L.append(x[1])
    c += 1
for x in ans:
    print(x[0] + 1, x[1] + 1)

Solution (Python):
def solve():
    (n, k) = map(int, input().split())
    p = [None] * (n + 1)
    w = [False] * (n + 1)
    a = []
    r = [None] * n
    i = 0
    b = (n + k - 2) // (k - 1)
    for c in map(int, input().split()):
        if p[c] is not None and (not w[c]):
            (X, Y) = (p[c], i)
            z = 0
            for (x, y) in a:
                L = max(x, X)
                R = min(y, Y)
                if L <= R:
                    z += 1
            if z < b:
                a.append((X, Y))
                r[c - 1] = str(X + 1) + ' ' + str(Y + 1)
                w[c] = True
        p[c] = i
        i += 1
    print('\n'.join(r))
solve()

Solution (Python):
def solve():
    (n, k) = map(int, input().split())
    p = [None] * (n + 1)
    w = [False] * (n + 1)
    a = []
    r = [None] * n
    i = 0
    b = (n + k - 2) // (k - 1)
    for c in map(int, input().split()):
        if p[c] is not None and (not w[c]):
            (X, Y) = (p[c], i)
            z = 0
            for (x, y) in a:
                L = max(x, X)
                R = min(y, Y)
                if L <= R:
                    z += 1
            if z < b:
                a.append((X, Y))
                r[c - 1] = str(X + 1) + ' ' + str(Y + 1)
                w[c] = True
        p[c] = i
        i += 1
    print('\n'.join(r))
solve()