You are not logged in. Please login at www.codechef.com to post your questions!

×

FAVGAME - Editorial

4
1

PROBLEM LINK:

Practice
Contest

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:

  1. There is a stack $S$ initially containing only the level $1$
  2. You pop the topmost level $x$ out of the stack
  3. 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.
  4. After completing level $x$ some $m_x$ new levels get unlocked
  5. You place all the $m_x$ unlocked levels on the top of the stack $S$ in an arbitrary order
  6. 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.

This question is marked "community wiki".

asked 12 Mar '17, 23:27

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 13 Mar '17, 15:22

admin's gravatar image

0★admin ♦♦
19.8k350498541


TLE Solution

Got TLE bcz called solve() twice

AC Solution

AC ==> called solve() Once

Too much Strict Time Limit

What if author set time limit as 2 seconds?

link

answered 14 Mar '17, 22:32

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

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)

link

answered 13 Mar '17, 17:49

xuanquang1999's gravatar image

5★xuanquang1999
1
accept rate: 0%

@pkacprzak: Why is dp[0][h] the answer?There is no predecessor of root anyways from where the h comes.Please help!

link

answered 13 Mar '17, 18:54

ps_1234's gravatar image

4★ps_1234
593
accept rate: 0%

edited 14 Mar '17, 07:03

@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. :-)

link

answered 14 Mar '17, 15:43

black_well's gravatar image

5★black_well
642
accept rate: 40%

@black_well thanks mate!

link

answered 14 Mar '17, 16:02

ps_1234's gravatar image

4★ps_1234
593
accept rate: 0%

@pkacprzak why answer is dp[1][h] ? I mean it could be dp[1][x] where x < h ? Please explain .. Thanks

link

answered 29 Mar '17, 18:43

shuklacoder55's gravatar image

3★shuklacoder55
142
accept rate: 0%

@alex_2008 the setters solution is even better than the editorial , Thank you Alexey Zayakin for such a solution :)

link

answered 31 Aug '17, 01:07

sonu_628's gravatar image

4★sonu_628
3458
accept rate: 8%

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 ii-th position in maskmask denotes that the ii-th 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 ?

link

answered 31 Aug '17, 23:24

pk301's gravatar image

3★pk301
62710
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×2,585
×2,167
×726
×707
×281
×124
×8

question asked: 12 Mar '17, 23:27

question was seen: 2,502 times

last updated: 31 Aug '17, 23:24