Lexicography (Editorial)

In this problem, the task is to distribute the given n \cdot l letters into $n$ words of length $l$, sorted lexicographically, so that the $k$-th word is as lexicographically small as possible.

The lexicographical order of words is determined character by character from left to right. Therefore, to minimize the $k$-th word, one must place the smallest possible letters in its earliest positions (starting from the left), without violating the lexicographical order of all words.

This leads to the following greedy algorithm:

1. Sort all the letters of the input string in ascending order.

2. Construct a two-dimensional array of characters

   v[1 .. n][1 .. l],

   where each row represents a separate word.

3. Fill the array column by column from left to right, since the columns correspond to positions in the words and determine their lexicographical order.

Filling the first column

1. In the first column, assign letters only to the rows with numbers from $1$ to $k$, using the $k$ smallest available letters.

2. Place these letters from top to bottom to maintain the lexicographical order.

3. The rows numbered k + 1, ..., n are not filled at this stage, as they do not affect the minimality of the $k$-th word.

This way, we ensure that the first character of the $k$-th word is minimal.

Filling the remaining columns

For each column j = 2, 3, ..., l:

1. Among the rows 1, ..., k, find the smallest index $pt$ such that the rows $pt$ and $k$ match in all previous columns 1, ..., j - 1.

2. The set of rows $[pt,k]$ consists of all words that are indistinguishable from the $k$-th word on the current prefix and therefore must remain no greater than it.

3. In column $j$, assign the smallest available letters only to the rows from $pt$ to $k$, from top to bottom.

4. 4. Repeat this process until all $l$ characters of the $k$-th word are fixed.

Filling the remaining cells

After the $k$-th word has been fully constructed:

• All remaining letters can be distributed arbitrarily, as long as the lexicographical order is not violated.

• • For example, the remaining letters can be filled into the array sequentially, row by row from top to bottom and left to right, in sorted order.

Correctness

• In each column, we minimize the current character of the $k$-th word.

• We assign identical or non-decreasing letters to all words that match the $k$-th word on the current prefix, so the order of the words is preserved.

• Once the $k$-th word is fully constructed, no further actions can make it larger.

Therefore, the resulting $k$-th word is lexicographically minimal.

Example

Let's consider the following test:

6 3 6
fgahhfgaaebdcbbebc

Here, we need to construct $6$ words of length $3$, using all the letters, so that the $6$th word in the lexicographically sorted list is minimal.

Sort the letters of the input string:

There are 18 = 6 \cdot 3 letters in total, which corresponds to a 6 × 3 table.

Column 1. Fill the first column with letters from top to bottom, from the first to the sixth row, since the sixth row is the one we are interested in.

Column 2. Now consider the rows whose prefix matches the prefix of the $6$th row. The prefix of the $6$th row after the first column is "$b$". The matching rows are $4,5$, and $6$. The smallest index among them is pt = 4.

In the second column, assign the smallest available letters to the rows numbered from $4$ to $6$.

Column 3. Again, we look for the rows whose prefix matches "$bc$" (after filling the first two columns). The matching rows are $5$ and $6$. The smallest index among them is pt = 5. Assign the smallest available letters to the rows numbered from $5$ to $6$. Now the $6$th word is fully constructed and equals "$bcd$".

Filling the remaining letters

After the $6$th word has been fixed, the remaining letters can be distributed in any valid way. For example, we can fill the table row by row from top to bottom and left to right with the remaining letters in lexicographical order.

Let's consider the first test case:

3 2 2
abcdef

Sort the letters of the input string:

We need to fill a matrix of $3$ words, each of length $2$, lexicographically minimizing the $2$nd word.

First, fill the first column with letters from top to bottom, only for the rows from $1$ to $2$, since these are the ones that affect the minimality of the $2$nd word.

Next, move to the second column. It should be filled starting from the earliest row whose prefix matches the prefix of the $2$nd row. In this case, that row is the $2$nd row itself, so pt = 2. Fill the second column with letters from row $pt$ to row $2$.

After that, distribute the remaining letters in lexicographical order, row by row from top to bottom and left to right, which completes the construction of a valid answer.

Algorithm implementation

Read the input data.

cin >> n >> l >> k;
cin >> s;

Sort the letters of the input string. Let the current letter being processed be $s[pos]$.

pos = 0;
sort(s.begin(), s.end());

Declare the result matrix $v$, consisting of $n$ rows and $l$ columns, where each row corresponds to a word of length $l$.

vector<string> v(n, string(l, ' '));

We'll distribute the letters in column $j$, filling the rows from $pt$ to k - 1 inclusive (row numbering starts from zero).

int pt = 0;
for (j = 0; j < l; j++)
{
  for (i = pt; i < k; i++)
    v[i][j] = s[pos++];

Move the pointer $pt$ forward (pt++) until the $j$-th character of the (k - 1)-th row matches the $j$-th character of row $pt$. As a result, $pt$ points to the row with the smallest index that currently matches the prefix of the (k - 1)-th row.

  while (v[pt][j] != v[k - 1][j]) pt++;
}

After that, fill the remaining cells of the matrix. To do this, go through the rows from top to bottom and the columns from left to right, distributing the remaining letters.

for (i = 0; i < n; i++)
for (j = 0; j < l; j++)
  if (v[i][j] == ' ') v[i][j] = s[pos++];

Print the answer.

for (i = 0; i < n; i++)
  cout << v[i] << endl;