The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

The reading experience is better on the blog

Preface: This solution may be rather verbose, mainly because I wrote down my entire thought process. Therefore, if you already have the basic idea, or if you are looking for a concise solution, you can skip this solution.

1: Understanding the Problem

There are $cow$ cows and $type$ classes of adjectives. There are $num_i$ adjectives in the $i$ th class, and the $j$ th adjective in the $i$ th class is $adj_{i,j}$ . Every cow must be modified, in order, by one adjective from each of these $type$ classes. You are told to remove $n$ of the $cow$ cows. Among the remaining $cow-n$ cows, after sorting them in lexicographic order, which cow is in position $k$ ?

2: Analysis and Problem Transformation

2.1: The Connection with Number Systems

This description alone may be somewhat abstract. Let us first look at the sample, then think about how to solve the problem on the basis of that sample.

In the sample, $n=3$ and $k=7$ . The values of $adj_{i,j}$ are as follows:

$adj_{i,j}$	$j=1$	$j=2$	$j=3$
$i=1$ (first adjective class)	“large”	“small”	N/A
$i=2$ (second adjective class)	“brown”	“white”	“spotted”
$i=3$ (third adjective class)	“noisy”	“silent”	N/A

Because the sample asks for the seventh cow in lexicographic order, we can first consider what the process of sorting by lexicographic order looks like.

For example, suppose the two strings “abc” and “cde” must be sorted lexicographically. We first compare the lexicographic order of the first characters, “a” and “c”; then compare the second characters, “b” and “d”; and only finally compare the third characters.

From this process, we can see that each character position has a different influence on the lexicographic order of the whole string. The first position has the greatest influence, and the last position has the least. We can therefore say that they have different “weights” in determining the lexicographic order of the complete string. If different strings are sorted from small to large lexicographically, then for any string, no matter how small the characters from the second position through the last position are, a very large first character will still place the string late in the ordering.

Looking again at the problem we need to solve, we can see that an adjective from the first class, such as “large”, has the greatest influence on the whole sequence of characters. An adjective from the second class, such as “brown”, has the next greatest influence, and the third class comes last.

At this point, I believe you can already sense the connection between this problem and a number system.

That connection is that, when comparing numbers, we also compare them from the highest digit to the lowest digit.

For example, consider the decimal number $(123456789)_{10}$ .

The digit $1$ represents the value $100000000$ , the largest value represented by any digit here ( $1$ is in the first position).

The digit $2$ represents $20000000$ , the second-largest represented value ( $2$ is in the second position).

A digit $x$ in position $i$ represents $10^{i-1}\times x$ , and the value represented by the complete decimal number is the sum of the values represented by all its digits.

Generalizing this rule to base $k$ , a digit $x$ in position $i$ represents $k^{i-1}\times x$ .

2.2: Solving a Simplified Problem

Here is the problem: whether we use the decimal system discussed above or a base- $k$ system, the mechanism is always “carry 1 upon reaching $k$ .” Consequently, the value represented by the digit 1 in position $i+1$ is necessarily $k$ times the value represented by the digit 1 in position $i$ . In this problem, however, the number of adjectives in each class is not necessarily the same.

We can first try to solve the case where every adjective class contains a fixed number of adjectives. Suppose every class contains $k$ adjectives. We first sort the adjectives in each class lexicographically and store the result in rank[i][j], where $i$ denotes the adjective class and $j$ denotes the rank.

The purpose of this step is to convert strings into numbers, making later calculations easier. We map every adjective to “digit $j$ in position $i$ ” of the number system. One point needs attention, however: the smaller the adjective-class number, the greater its influence on the overall lexicographic order, whereas the smaller the digit position in an ordinary number, the smaller its influence on the number’s total value.

Because we have completed the mapping from adjectives to numbers, the next task is equivalent to converting a decimal number to base $k$ , then converting the resulting digits back into the corresponding strings.

This may still sound abstract, so let us simulate the process.

Suppose the first adjective class is {"a","b"}, the second is {"c","d"}, and the third is {"e","f"}.

We can then obtain the following rank array. The ranks start from 0 to make calculation convenient.

$rank_{i,j}$	$j=0$	$j=1$
$i=1$ (first adjective class)	“a”	“b”
$i=2$ (second adjective class)	“c”	“d”
$i=3$ (third adjective class)	“e”	“f”

If we want the cow in the third lexicographic position, we first find the binary representation of 3, namely $(011)_2$ . We then reverse the number to obtain $(110)_{2\text{ reversed}}$ . This reversal is necessary because a smaller adjective-class number has a greater influence on the overall lexicographic order, while a smaller digit position has a smaller influence on a number’s total value. Finally, map $(110)_{2\text{ reversed}}$ back to the corresponding strings, with each position corresponding to its respective class. The final answer is “a, d, f”.

2.3: Solving the Original Problem

While solving the simplified problem, we mapped each adjective class to a digit position in the number system, mapped its rank $j$ to digit $j$ , and made the number of adjectives in each class the base of the number system.

We can see that the key to the original problem is the base. In the simplified problem, every digit position in the number system had the same base, and every adjective class contained a fixed number of adjectives. In the actual problem, the number of adjectives differs among classes, so the base must also change from one digit position to another.

Return to the sample. The numbers of adjectives in the respective classes are $num_1=2$ , $num_2=3$ , and $num_3=2$ .

We mapped the third adjective class to the first digit of the number system, the second class to the second digit, and similarly the first class to the third digit.

We can therefore specify that the number system is binary in its first digit, ternary in its second digit, and binary again in its third digit.

Although this mixed base of “ $2,3,2$ ” can describe every possible cow, solving the problem also requires converting a decimal number into this mixed-radix representation.

Everyone is surely familiar with converting decimal to binary. For example, to convert a decimal number $a$ into an $x$ -digit binary number $b$ , start with the highest digit $x$ of $b$ . At each step, calculate $\lfloor a \div (\text{the value represented by this digit of }b\text{ in decimal})\rfloor$ , then calculate $a = a \bmod (\text{the value represented by this digit of }b\text{ in decimal})$ .

Written as a program, it looks like this:

// k is the decimal number.
// weight_in_pos[i] is the decimal value represented by digit i, counting from the highest digit,
// which is the reverse of the ordinary convention.
// i is the current digit, also counted from the highest digit in the reverse convention.
for (int i = 1; i <= adj_num; i++)
{
    cout << adj_by_pos[i][(k) / weight_in_pos[i]] << " ";
    k %= weight_in_pos[i];
}

Thus, for a mixed radix such as “ $2,3,2$ ”, we need only precompute the decimal value represented by every digit position, after which we can convert a decimal number into that mixed radix.

The decimal value represented by a position means the decimal value obtained when that position is 1 and every other position is 0 in the original radix system.

How do we calculate the decimal value represented by each position in such a system?

In any radix system, as long as two numbers use the same radix system, the value represented by a number with more digits must be greater than the value represented by one with fewer digits.

We can therefore calculate the decimal value represented by position $i$ as the decimal value represented by position $i-1$ , multiplied by the largest digit that position $i-1$ can represent plus 1. This ensures that a number with more digits is always greater than one with fewer digits. We can also see that the largest digit plus 1 is exactly the base of that position; for example, the largest digit in binary is 1.

With this conclusion, we can recursively calculate the decimal value represented by every position. Store the result in weight_in_pos[i], which is the value represented by position $i$ , and initialize the value represented by the first position to 1.

In the sample’s “ $2,3,2$ ” radix system, the decimal value represented by the first position is initialized to 1. The weight_in_pos value for the second position is $1\times2=2$ , and the value for the third position is $2\times3=6$ .

At this point, we can calculate the cow in position $k$ among all possible cows. The problem, however, asks which cow is in position $k$ among the remaining $cow-n$ cows after lexicographic sorting.

This small issue is relatively easy to solve. We can transform $k$ into a rank among all cows rather than a rank among only the remaining cows. First calculate the ranks, among all cows, of the $n$ cows that must be removed. If one of those $n$ cows has a rank less than or equal to $k$ , increment $k$ by 1. This is equivalent to saying that some of the first $k$ cows cannot be selected; because we still need to select $k$ cows, we must account for every removed cow whose rank is smaller than $k$ .

Code and Details

All details are explained in the comments.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, k;
int adj_num = 0;
vector<string> str[105];          // str[i] denotes the adjectives that describe cow i.
vector<string> adj_by_pos[35];    // adj_by_pos[i] denotes all adjectives that appear in position i.
set<string> is_appear[35];        // is_appear[i] determines whether an adjective has appeared in position i.
int weight_in_pos[35];            // The value represented by each position (its lexicographic rank).
map<string, int> rank_in_pos[35]; // rank_in_pos[i][j] is the lexicographic rank of string j in position i.
int cow_rank[105];                // Ranks of the cows Farmer John does not have.
bool debug = false;               // Debug switch; enable it to experience the solution process.
void mapping()                    // Sort each adjective class lexicographically and store the result in rank[i][j],
{                                 // where i is the adjective class and j is the rank. Ranks start from 0 because
                                  // this maps words to numbers, and numbers start from 0.
    for (int i = 1; i <= adj_num; i++)
    {
        int rank = 0;
        for (auto j : adj_by_pos[i]) // A C++11 feature: use j to traverse every element of adj_by_pos[i].
        {
            rank_in_pos[i][j] = rank;
            if (debug)
                cout << j << " rank = " << rank << " i = " << i << endl;
            rank++;
        }
    }
}

int get_pos(int cow_id)
{
    int ans = 0;
    for (int i = 1; i <= adj_num; i++)
    {
        ans += weight_in_pos[i] * (rank_in_pos[i][str[cow_id][i - 1]]);
    }
    return ans + 1; // The answer can be 0, but ranks should start from 1.
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    string temp_str;
    for (int i = 1; i <= n; i++)
    {
        cin >> temp_str;
        while (temp_str != "no")
        {
            cin >> temp_str;
        }
        int adj_pos = 1;

        while (1)
        {
            cin >> temp_str;
            if (temp_str == "cow.")
            {
                break;
            }
            str[i].push_back(temp_str);
            if (!is_appear[adj_pos].count(temp_str)) // It has not appeared before; this is deduplication.
            {
                adj_by_pos[adj_pos].push_back(temp_str);
                is_appear[adj_pos].insert(temp_str);
            }
            if (i == 1)
            {
                adj_num++; // Calculate the number of adjective classes.
            }
            adj_pos++;
        }
    }
    for (int i = 1; i <= adj_num; i++)
    {
        sort(adj_by_pos[i].begin(), adj_by_pos[i].end()); // Sort the adjectives in each class.
    }

    weight_in_pos[adj_num + 1] = 1;            // The number represented by the first position should be 1.
    adj_by_pos[adj_num + 1].push_back("temp"); // 1 times 1 is 1, so push one element to make the size 1.

    for (int i = adj_num; i >= 1; i--) // Calculate the decimal value represented by each position; the order of
    {                                  // positions here is reversed from the ordinary convention because adjective
                                       // classes and number-system “positions” run in opposite directions.
        if (debug)
            cout << "i" << i << endl;
        weight_in_pos[i] = weight_in_pos[i + 1] * adj_by_pos[i + 1].size();
    }
    mapping();
    for (int i = 1; i <= n; i++)
    {
        cow_rank[i] = get_pos(i); // Calculate the overall ranks of the n cows that must be removed.
        if (debug)
            cout << "cowrkw " << i << " = " << cow_rank[i] << endl;
    }
    sort(cow_rank + 1, cow_rank + n + 1); // Sort the cows by the rank of each type.
    for (int i = 1; i <= n; i++)
    {
        if (cow_rank[i] <= k)
        {
            k++;
        }
        else
        {
            break;
        }
    }
    k--; // k originally denotes the cow's ordinal rank, but we converted the cow's rank into a number.
         // The smallest cow has number 0 rather than 1, so subtract 1 here.
    if (debug)
        cout << "new k" << k << endl;
    for (int i = 1; i <= adj_num; i++)
    {
        cout << adj_by_pos[i][(k) / weight_in_pos[i]] << " ";
        if (debug)
            cout << "i " << i << " (k) / weight_in_pos[i] " << (k) / weight_in_pos[i] << endl;
        k %= weight_in_pos[i];
    }
    system("pause");
}

That is the end of the solution. If you find a problem with it or encounter something you cannot understand, you are welcome to send me a private message or leave a comment. If you found it helpful, please give it a like. Thank you.