Editorial for COCI '22 Contest 5 #4 Slastičarnica

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.

Let dp(l, r) be the maximum number of customers we can serve if we still have cakes a_l, a_{l+1}, \dots, a_r at the table. For the first subtask, we can use the simple transition:

\displaystyle dp(l, r) = \max\left(\max_{i=0}^{i<l} (dp(i, r)+check(i, l-1, dp(i, r))), \max_{j=r+1}^{j<n} (dp(l, j)+check(r+1, j, dp(l, j)))\right)

where check(L, R, x) is a function that returns 1 if it is possible to satisfy customer x with the cakes a_L, a_{L+1}, \dots, a_R, and 0 otherwise. Time complexity is \mathcal O(n^3) or \mathcal O(n^4), depending on the implementation of the function check.

Similarly, for the second subtask if all d_i are equal to 1, then we only need to check dp(l-1, r) and dp(l, r+1) to determine dp(l, r).

That leads us to the complete solution. Is it possible somehow to check only neighbouring states and get the required solution? It is! Instead of memorizing only the maximum number of customers we can serve, we will memorize two more things: the biggest number of cakes that is possible to give to the current customer outside the left and the right border. For example, let k be the number of cakes we can give to the current customer outside of the left border. Two things need to be satisfied:

  • dp[l-k][r] = x (it is possible to give all the cakes to the current customer)
  • a_{l-k}, a_{l-k+1}, \dots, a_{l-1} \ge s_x (all the cakes have sweetness greater or equal to the required value)

Now we do not need to check every state, only the neighbouring ones. When one of the counters becomes equal to d_x, we can give those cakes to the current customer, and increase the customer number by 1. Total time complexity is \mathcal O(n^2).


There are no comments at the moment.