Editorial for DMOPC '14 Exam Time P5 - Happy Teachers

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.

By Eduard Ionescu

Notice that this problem is very similar to the standard 0-1 Knapsack Problem, and that the total happiness provided by a teacher for all amounts of time until their happiness level reaches zero due to the energy consumption can be calculated. As such, they can be treated as separate objects; however, they must all be processed simultaneously instead of sequentially so that a teacher's first second in the video won't appear twice. Remember to keep track of the video duration for the total happiness of each total preparation time and to obtain the minimum duration for the maximum total happiness.

$\mathcal{O}(n \cdot s)$ ~\mathcal{O}(n \cdot s)~

Comments

1

Riolku commented on Dec. 20, 2018, 6:30 p.m. ← edited →

Since each teacher has $s/P$ ~s/P~ possible ways to contribute to the video, there are $s/P$ ~s/P~ weights to process after each steps, with $s$ ~s~ steps. This should make the solution $\mathcal{O}(ns^2)$ ~\mathcal{O}(ns^2)~. Please explain to me why this is not the case or change the editorial to match.