Subtask 1

For the first subtask, we can permute all possible orders of the dishes and students and for each permutation, we can check if the configuration is valid.

Time complexity: ~\mathcal{O}(N!^2 \times N^2)~

Subtask 2

The second subtask assumes that the dishes can always be arranged in the order ~1,2,\dots,N~ if any solution exists. Therefore, each student can be represented as a range ~[l,r]~, where ~l~ is the lowest number of the dish they want, and ~r~ is the highest number. Observe that a student without any dish can be placed anywhere in the line. Now, we take the remaining students, sort the students by ranges, and check if their ranges do not overlap anywhere except for the endpoints of ranges. If this condition is true, we can iterate through the dishes and print out any student whose range begins on the dish.

Be mindful that the last student to be printed out for each dish is the student whose range does not end at that dish.

Time complexity: ~\mathcal{O}(N \log N)~

Subtask 3

For the third subtask, we need to make some more important observations about the problem. First, we will define a student/dish without any corresponding dish/student as unimportant. Second, we will define a student/dish with exactly 1 dish/student as lonely. All other dishes and students will be called important. Similar to the previous subtask, unimportant dishes/students can be placed anywhere in our final order.

Note that a plate cannot have more than 2 important students. Similarly, a student cannot want more than 2 important plates. Also, there cannot be any cycles. Therefore, if we ignore all other dishes and students and treat the remaining ones as a graph, we should have only linear graphs. We can use any graph search technique to see if this property holds true.

We can keep track of the order of dishes/students during our graph search by performing the following actions at each student/dish we visit: adding all connected lonely dishes/students in any order, followed by the next dish/student. Again, we can place unimportant dishes/students anywhere in our order. Note that components of the graph can be placed in any order as well.

Well-versed programmers may recognize that every component must form a caterpillar tree.

Time complexity: ~\mathcal{O}(\sum_{i=1}^N d_i)~