PROBLEM LINK:
Author: Alexey Zayakin
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak
DIFFICULTY:
Medium
PREREQUISITES:
Trees, dynamic programming
PROBLEM:
The goal of the problem is to complete a video Game in a few days as possible. The Game has n levels numbered from 1 to n and you can play it at most h \leq 24 hours per day. The i-th level takes t_i \leq h hours to complete. The levels are structured in a tree T. It means that the level 1 is the root of the tree and the only unlocked level available to play at the beginning. Every other level i has unique level, its parent in the tree denoted as parent_i, such that completing level parent_i unlocks level i making it available to play. The game is completed when all its levels are completed. Moreover, the process of completing the game looks as follows:
- There is a stack S initially containing only the level 1
- You pop the topmost level x out of the stack
- You spends t_x hours to complete level x and you must complete it during a single day, which means that if there are not enough hours to complete level x on the current day, you cannot start it on that day.
- After completing level x some m_x new levels get unlocked
- You place all the m_x unlocked levels on the top of the stack S in an arbitrary order
- If stack S is empty, the Game is considered completed, otherwise you go back to the step 2
The task is to find the minimum number of days needed to complete the Game.
QUICK EXPLANATION:
Use dynamic programming to compute for each vertex v the minimum number of days needed to complete all levels in v's subtree when you start on day 1 in v and have already worked p hours on that day.
EXPLANATION:
First and major observation we can make is to notice that each valid play, i.e. the order in which levels of the game are unlocked, corresponds to DFS order on T. Thus, the problem is reduced to finding DFS order which yields the smallest cost of visiting all N nodes of T.
Subtask 1
In the first subtask, we have N \leq 9, which allows totally brute-force solution. Notice that there are no more than N! possible DFS orders of T, so one can generate all N! permutation of the nodes, take only the ones describing valid DFS orders, and for each such sequence, compute the number of days needed to complete the game unlocking levels in the order given by the sequence. The result is the minimum result among all such valid DFS sequences. The time complexity of this method for a single test case is (N! \cdot N).
Subtasks 2, 3, 4
Approaches for subtasks 2, 3 and 4 are based on dynamic programming approach, so let’s describe the idea first. Just to recall, notice that h \leq 24 and each node has at most 10 children. Both these constraints are very important here.
Let dp_{v, p} be a pair (a, b) denoting that when we start processing v's subtree on the first day and have already worked p hours that day, then a is the minimum number of additional days, besides the first day, to complete the whole v's subtree and b is the minimum number of hours we have to work on the last day in such optimal solution. Now, by this definition, dp functions captures all information we need, and the result to the problem is the resulting number of days in dp_{1}{h}, because 1 is the root of the tree and completing its subtree means that the whole game is completed, and its always not worse to work as many hours on the first day as possible.
Now, notice that for fixed v and p, the value of dp_{v, p} can be easily computed when we only know the best order in which we should complete subtrees of children of v. More specifically, if we know such best order, then we first complete level v, because it has to be completed before any other levels in v's subtree, and then we solve the problem recursively for all v's children. Next, we just compute the value of dp_{v,p} straight away by accumulating, in a deterministic way, values computed for v's children in such an order. Thus, the problem is reduced to just computing the best order of processing subtrees of v's children.
Subtask 2
In the second subtask, there is an additional constraint on the number of children of a node, and we know that each node has at most 2 children. This allows for a fixed node v to just check at most 2! = 2 orders of completing subtrees of v's children and assign the smallest result to dp_{v,p}.
Subtask 3
In the third subtask, we have N \leq 100 and h \leq 8. These constraints allow to use the intended method for the original constraints but just implemented in not an optimal way. For example, one can capture additional, not necessary information in states of dp, resulting in higher complexity of the solution than the intended one.
Subtask 4
In the fourth subtask, we have the original constraints, and the only thing left to do is to show how for a fixed v and p, compute the best order of completing subtrees of v's children resulting in the smallest value of dp_{v,p}. Just to recall, we know that v has at most 10 children, so there are at most 10! possible such orders, but, since this number is quite big, checking just any of them explicitly is unacceptable.
However, a quite common optimization can be used here. We can avoid iterating over all permutations of children and instead iterate over all subsets of them. For a fixed node v, let f_{mask, p} be a pair (a, b) denoting that when we start processing v's subtree on the first day and have already worked p hours that day, then a is the minimum number of additional days, besides the first day, to complete level v and subtrees of v's children included in the mask, and b is the number of hours we have to work on the last day in such optimal solution. Then, set mask can be implemented as a binary number of length m_v, where 1 at the i-th position in mask denotes that the i-th children is included into the set. Now, we can just iterate over all masks and extend a solution for a fixed mask to a mask_{new} having one more subtree completed than mask. Then, the value of dp_{v,p} is just the value of f_{mask_{full}, p}, where mask_{full} denotes a set of all children of v.
The overall time complexity of this method is O(N \cdot h \cdot 2^{10}). For implementation details of this exact method please refer to setter solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
