[Solution] Ela Sorting Books solution codeforces

Ela Sorting Books solution codeforces – Ela loves reading a lot, just like her new co-workers in DTL! On her first day after becoming an engineer in DTL, she is challenged by a co-worker to sort a heap of books into different compartments on the shelf.

𝑛n books must be split into 𝑘k compartments on the bookshelf (𝑛n is divisible by 𝑘k). Each book is represented by a lowercase Latin letter from ‘a’ to ‘y’ inclusively, which is the beginning letter in the title of the book.

Table of Contents

[Solution] Ela Sorting Books solution codeforces

Ela must stack exactly 𝑛𝑘nk books in each compartment. After the books are stacked, for each compartment indexed from 11 to 𝑘k, she takes the minimum excluded (MEX) letter of the multiset of letters formed by letters representing all books in that compartment, then combines the resulting letters into a string. The first letter of the resulting string is the MEX letter of the multiset of letters formed by the first compartment, the second letter of the resulting string is the MEX letter of the multiset of letters formed by the second compartment, … and so on. Please note, under the constraint of this problem, MEX letter can always be determined for any multiset found in this problem because ‘z’ is not used.

What is the lexicographically greatest resulting string possible that Ela can create?

A string 𝑎a is lexicographically greater than a string 𝑏b if and only if one of the following holds:

  • 𝑏b is a prefix of 𝑎a, but 𝑏𝑎b≠a;
  • in the first position where 𝑎a and 𝑏b differ, the string 𝑎a has a letter that appears later in the alphabet than the corresponding letter in 𝑏b.

The minimum excluded (MEX) letter of a multiset of letters is the letter that appears earliest in the alphabet and is not contained in the multiset. For example, if a multiset of letters contains 77 letters ‘b’‘a’‘b’‘c’‘e’‘c’‘f’ respectively, then the MEX letter of this compartment is ‘d’, because ‘d’ is not included in the multiset, and all letters comes before ‘d’ in the alphabet, namely ‘a’‘b’ and ‘c’, are included in the multiset.

[Solution] Ela Sorting Books solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1001≤t≤100). Description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑘k (1𝑛2001≤n≤2001𝑘𝑛1≤k≤n). It is guaranteed that 𝑛n is divisible by 𝑘k.

The second line of each test case contains a string of 𝑛n lowercase Latin letters from ‘a’ to ‘y’ inclusively. Each letter represents the starting letter of the title of a book in the initial heap.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 10001000.

Output

For each test case, output a string of 𝑘k letters which is the most optimal string that Ela can find.

Example

input

Copy
5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5

[Solution] Ela Sorting Books solution codeforces

output

Copy
edb
ccbbba
bbbbbaaaaaaa
z
aaaaa

[Solution] Ela Sorting Books solution codeforces

In the first test case, the books can be divided into 33 compartments as below:

  • the first compartment contains the books with indices 1,2,3,71,2,3,7𝑚𝑢𝑙𝑡𝑖𝑠𝑒𝑡1={multiset1={‘c’‘a’‘b’‘d’}}  𝑀𝐸𝑋(𝑚𝑢𝑙𝑡𝑖𝑠𝑒𝑡1)=MEX(multiset1)= ‘e’
  • the second compartment contains the books with indices 4,5,6,94,5,6,9 : 𝑚𝑢𝑙𝑡𝑖𝑠𝑒𝑡2={multiset2={‘c’‘c’‘a’‘b’}}  𝑀𝐸𝑋(𝑚𝑢𝑙𝑡𝑖𝑠𝑒𝑡2)=MEX(multiset2)= ‘d’
  • the third compartment contains the remaining books 8,10,11,128,10,11,12 : 𝑚𝑢𝑙𝑡𝑖𝑠𝑒𝑡3={multiset3={ ‘a’‘a’‘a’‘c’}}  𝑀𝐸𝑋(𝑚𝑢𝑙𝑡𝑖𝑠𝑒𝑡3)=MEX(multiset3)= ‘b’

Therefore, the answer is ‘edb’. It can be proven that there is no way that Ela can arrange the books so that it results in a lexicographically greater string.

For Solution

“Click Here”

Leave a Comment