Editorial for DMOPC '18 Contest 3 P4 - Bob and English Class


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: r3mark

For the first subtask, it's optimal to connect the rightmost to the leftmost, second rightmost to the second leftmost, etc. A prefix sum can be used to speed this up.

Time Complexity: \mathcal{O}(N)

For the second subtask, precompute the distance between each pair of students using BFS or DFS. Then, brute-force all possible configurations of pairs.

Time Complexity: \mathcal{O}(KN+K!)

For the third subtask, root the tree arbitrarily. We think of the distances between pairs as each student moving up to their LCA. Now let dp[i][j] be the total cost within the subtree of node i such that j students are still moving up. Now, we must be able to merge a node's children's dp values. Given a set of the children's j's, note if we can find the minimum j for the node, we can obtain any larger j with the same parity and within the total sum of the j's and the node's number of students. By considering this problem, we only need to consider the maximum j, and the sum of the j's. So it can be done in polynomial time. The final answer is dp[1][0].

Time Complexity: \mathcal{O}(NK^3)

For the final subtask, we realize that the solution to the third subtask is absolutely awful. Root the tree at the centroid of the students (not the centroid of the entire tree!). Again, consider this problem. If we merge the children of the centroid with their maximum possible j's, then we can actually obtain 0, which means that all the students have been paired up. Also, since the children of the centroid have maximum possible j's, this must be the maximum possible total. So the optimal case is when all the students head to their centroid. This can be implemented in linear time.

Time Complexity: \mathcal{O}(N+K)


Comments

There are no comments at the moment.