Editorial for Mock CCC '22 Contest 2 J5 - Dominating the Olympics

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.

Author: uselessleaf

All the events Tommy can complete can be represented as a DAG with the uncompletable events ignored. In this case, we will let the nodes represent the events, and we will have an edge from node i to j if and only if event i must be done before event j. The answer to the problem is then the longest path in this DAG, since all the other events can be overlapped with events in the longest path.

We can find the longest path with a dynamic programming approach. Let dp[i] represent the longest path starting from node i, and time[i] represent the time for event i. We then obtain the following recurrence:

dp[i] = 0
for each outgoing edge of i:
    dp[i] = max(dp[i], dp[destination node of that edge])
dp[i] += time[i]

The answer is then the max value in the dp array.

Time Complexity: \mathcal{O}(V+E)


There are no comments at the moment.