Editorial for Another Contest 5 Problem 5 - Another Cheese Problem


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.

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 x_1 through operations x_k 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 f(n) be the minimum number of bowls needed to complete operation n. If n does not depend on any operations, f(n) is equal to 1. Otherwise, consider the operations x_1 through x_k that operation n directly depends on, and compute f(x_1) through f(x_k). Assume without loss of generality that f(x_i) \ge f(x_{i+1}) for 1 \le i \le k-1. f(n) is therefore equal to \max(k+1, f(x_1), f(x_2)+1, \dots, f(x_k) + (k-1)).

This runs in \mathcal O(N \log N) if done naively, and can be optimized to \mathcal O(N) though that improvement is not necessary.


Comments


  • 2
    LanceDragon  commented on July 22, 2019, 5:30 a.m.

    Can someone explain more the editorial ??


    • 0
      Java12345  commented on Feb. 8, 2020, 9:44 p.m.

      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!


    • 2
      Riolku  commented on July 22, 2019, 11:44 a.m.

      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.