PROBLEM LINK:Author: Alexey Zayakin 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:
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 1In the first subtask, we have $N \leq 9$, which allows totally bruteforce 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, 4Approaches 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 2In 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 3In 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 4In 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:
This question is marked "community wiki".
asked 12 Mar '17, 23:27

Got TLE bcz called solve() twice AC ==> called solve() Once Too much Strict Time Limit What if author set time limit as 2 seconds? answered 14 Mar '17, 22:32

Is it possible to solve this problem if the "level holder" is a queue instead of a stack? (Btw that's exactly how did I misread the problem) answered 13 Mar '17, 17:49

@pkacprzak: Why is dp[0][h] the answer?There is no predecessor of root anyways from where the h comes.Please help! answered 13 Mar '17, 18:54

@ps_1234: dp[0][h] denotes the minimum number of days excluding first day require to complete all the level. This means than the current day is not counted in dp. So, if chef starts the game from the next day, then the first day will counted in the answer. In short, dp[0][h] is same as (dp[0][0] + 1) where dp[0][0] denotes that the minimum number of days, besides the first day, require to complete the game if chef starts the game on first day without wasting any hour. i.e p=0. So, you need to add 1 i.e. first day in your final answer. So, (dp[0][0] + 1) is also a valid answer and is easy to understand,too. I hope this may solve your query. :) answered 14 Mar '17, 15:43

@pkacprzak why answer is dp[1][h] ? I mean it could be dp[1][x] where x < h ? Please explain .. Thanks answered 29 Mar '17, 18:43

@alex_2008 the setters solution is even better than the editorial , Thank you Alexey Zayakin for such a solution :) answered 31 Aug '17, 01:07

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 vv, let fmask,pfmask,p be a pair (a,b)(a,b) denoting that when we start processing vv's subtree on the first day and have already worked pp hours that day, then aa is the minimum number of additional days, besides the first day, to complete level vv and subtrees of vv's children included in the maskmask, and bb is the number of hours we have to work on the last day in such optimal solution. Then, set maskmask can be implemented as a binary number of length mvmv, where 11 at the iith position in maskmask denotes that the iith children is included into the set. Now, we can just iterate over all masksmasks and extend a solution for a fixed maskmask to a masknewmasknew having one more subtree completed than maskmask. Then, the value of dpv,pdpv,p is just the value of fmaskfull,pfmaskfull,p, where maskfullmaskfull denotes a set of all children of vv. can anyone please explain how this works ? answered 31 Aug '17, 23:24
