Colors and Intervals
Contest: Codeforces Global Round 15
Difficulty rating: 2300
Tags: constructive algorithms, data structures, 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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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:

Example input:
4 3
2 4 3 1 1 4 2 3 2 1 3 4

Example output:
4 5
1 7
8 11
6 12

Example input:
1 2
1 1

Example output:
1 2

Editorial:
Solution 1
We describe the algorithm and later we explain why the construction works.
Let $$$x_{i, j}$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le k$$$) denote the position of the $$$j$$$-th occurrence of color $$$i$$$ (from the left).
First, sort the colors according to $$$x_{i, 2}$$$. Take the first $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ colors, and to each of them assign the interval $$$[x_{i, 1}, \, x_{i, 2}]$$$. Then, sort the remaining colors according to $$$x_{i, 3}$$$, take the first $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ and to each of them assign the interval $$$[x_{i, 2}, \, x_{i, 3}]$$$.
More generally, in the $$$t$$$-th step: sort the remaining colors according to $$$x_{i, t + 1}$$$; take the first $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ (possibly less in the last step) of these colors; assign to each color $$$i$$$ the interval $$$[x_{i, t}, \, x_{i, t + 1}]$$$.
Let us show that this choice of intervals works. It is straightforward to see that the first two properties hold.
It remains to check the third property. We prove that two intervals selected in different steps are disjoint. Since in each step we select at most $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals, this is sufficient to conclude. Consider two colors $$$i, \, j$$$ selected in two different steps $$$s < t$$$ respectively. Then, we have $$$x_{i, s + 1} < x_{j, s + 1} \le x_{j, t}$$$ and thus $$$[x_{i, s}, \, x_{i, s + 1}] \cap [x_{j, t}, \, x_{j, t + 1}] = \varnothing$$$, which is exactly what we wanted to prove.
Complexity: $$$O(nk)$$$.
$$$$$$$$$$$$
Solution 2
A greedy approach is also possible.
Let $$$x_{i, j}$$$ be defined as in Solution 1. Consider all intervals of the form $$$[x_{i, j}, \, x_{i, j + 1}]$$$ and sort them increasingly according to their right endpoint. We now iterate over these intervals, and for each of them, we decide to select it if both these conditions are met (which are equivalent to "selecting the interval does not violate any requirement"):
• no interval of the same color has been chosen yet;
• among the numbers spanned by the interval, no one is contained in (at least) $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ already selected intervals.
Let us prove that this algorithm works (i.e., it selects exactly one interval for each color). Suppose, by contradiction, that, for some color $$$i$$$, no interval of that color gets chosen. This means that, for each $$$1 \le j \le k - 1$$$, there exist $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ selected intervals that intersect interval $$$[x_{i, j}, \, x_{i, j + 1}]$$$. We can say more: the rightmost endpoints of these intervals must belong to $$$[x_{i, j}, \, x_{i, j + 1}]$$$; indeed, if it weren't the case for at least one interval $$$[a, \, b]$$$, the interval $$$[x_{i, j}, \, x_{i, j + 1}]$$$ would come before $$$[a, \, b]$$$ in the ordering, so it would actually have been selected. Since all these intervals must be distinct, they are $$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$. Yet this contradicts the fact that they must be at most $$$n - 1$$$, one for each color other than $$$i$$$.
Complexity: $$$O(n^2k)$$$.