## Editorial for Another Contest 5 Problem 5 - Another Cheese Problem

**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.**

An obvious lower bound for the number of bowls that is needed is the maximum number of operations one operation directly depends on, plus one. This is directly implied by the problem statement.

However, this figure is not always attainable. By way of contradiction, let operation 1 be dependent on operations 2 and 3. If we know a priori that both operations need 10 bowls to complete, then we actually need 11 bowls to complete operation 1. We arbitrarily pick one of the operations to complete, and then we need to allocate one bowl to store that intermediate result, and then we need 10 more bowls to complete the other operation.

This leads us to our first critical realization - given operations through operations that operation 1 directly depends on, we should not interleave intermediate operations from two distinct ones. Therefore, we should select some operation and commit to finishing it before switching to another one that operation 1 depends on.

What order should we commit to finishing them in? Intuitively, we should commit to the operations which use the most bowls first. Formally, let be the minimum number of bowls needed to complete operation . If does not depend on any operations, is equal to . Otherwise, consider the operations through that operation directly depends on, and compute through . Assume without loss of generality that for . is therefore equal to .

This runs in if done naively, and can be optimized to though that improvement is not necessary.

## Comments

Can someone explain more the editorial ??

In the 4th paragraph, f(n) should equal max(k+1, max(f(xi)+

k-1-i)). The k+1 comes from assuming you need one bowl for each of the previous operations. The f(xi) part makes sure this is greater than or equal to other maximums you've already found, and the +k-i-1 covers the scenario in the second paragraph of the editorial. Good luck!If the question can be answered quickly, could you explain what is causing you trouble? In either case, I would strongly reccomend joining the DMOJ Slack where we can give more detailed help.