In order to find a simple and elegant solution, it is important to notice that since each student can participate in a single category, but multiple students can compete in the same category, and each student has applied for all categories, it suffices to determine for each student the category which they know best. Then we can select the best ~K~ students, judging only by the category which they are best in.

Why is that solution correct? Precisely because any number of students can compete in the same category. If a student is selected to participate in a category, other students are not restricted in their category choice - only the selected student is prevented from competing in any additional categories. It follows that we have to determine for each student the category which they know best.

There are two possible implementations; one requires sorting, while the other one doesn't.

Solution

For each student, we determine the category which they know best. Now we have each student's knowledge represented by a single number. We can simply sort students by that number and select the first ~K~ students from the sorted sequence.

Time complexity is ~\mathcal O(NM + N \log N)~. Memory complexity is ~\mathcal O(N)~.

Alternative solution

We can take advantage of the fact that students are already sorted by categories. For each category, we keep a pointer to the first (best) student. In each of ~K~ steps, we iterate over all categories and determine the category that contains the pointed-to student with the most knowledge. We add that student's knowledge to the result and move the pointer to the next best student in that category (the following one, since they are already sorted by category). It is also necessary to keep track of students that have already been selected, since they must be skipped if encountered again.

Time complexity is ~\mathcal O(NM)~. Memory complexity is ~\mathcal O(NM)~.