Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage
  1. Home
  2. /
  3. Codeforces
  4. /
  5. Contests
  6. /
  7. Educational Codeforces Round 25
  8. /
  9. E. Minimal Labels
  10. /
  11. Hints: Minimal Labels

Hints: Minimal Labels

Which vertices are possible candidates for being assigned the label 1? Among these vertices, which one should get the label?
Suppose there are 5 vertices with indegree zero. Which one of them will have label 1, 2, 3, 4 and 5?
Sort those 5 vertices. Assign 1 to the smallest and 5 to the highest.
The answer above for Hint 2 is wrong. Why?
We should not assign all the 5 labels at once. We should only assign label 1 to the smallest vertex, and then remove it from the graph. This will “unlock” new vertices. And then, we can apply the smallest label to the smallest unlocked vertex. This is exactly like the topological sort algorithm, where we progressively unlock vertices. Implement this approach.
The answer for hint 3 is wrong as well. If you implement it, you will get WA6. Can you think of a testcase or prove why your solution and innocent looking proof is incorrect? That is most educational part of the problem.

We were smart enough to figure out that instead of assigning all 5 labels at once, we should assign label 1 and unlock some vertices. However, notice that label 1 is most precious. What if you had unlocked new vertices by utilising the less valuable labels, for example, label 5? In that case, you might have gotten better candidates for Label 1.

Assign the least valuabel valuable (Label 5) and unlock new vertices. Is this strategy correct?

Even this strategy is wrong. What if the most important candidate for label 5 is hiding behind vertex 4?

Consider this counter example.

4 --> 1
2 --> 3

The least valuable label is Label n. Hence, if we can assign this to the least valuable candidate that can afford this label, then we will always preserve the important labels for important candidates.

Using this, come up with an algorithm to solve the problem.

Candidates for label n are vertices with outdegree 0. Amongst these candidates, you should assign the label to the one with highest index. Then, delete this vertex from the graph, unlocking a new set of vertices with outdegree zero.

Why is the algorithm correct? How do you delete sink vertices from a graph? How do you efficiently retrieve the highest index vertex with outdegree 0?

To delete a sink vertex, use the topological sort technique on the Transpose Graph. To efficiently retrieve highest index vertex, use a set with keys (outdegree, index) with a custom comparator that sorts it by smaller outdegree first and then bigger index next.