Editorial for Riolku's Mock CCC S4 - Clumsy Cindy


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.

Author: Plasmatic

Subtask 1

This subtask was intended to reward brute force solutions.

Time Complexity: \mathcal{O}(3^N)

Subtask 2

There are many possible DP solutions to the problem, but we'll only expand on one here.

Let dp[i][j] be the minimum number of fill operations needed to fill the first i buckets such that the fill operation was used on bucket i exactly j times. For this subtask, we can brute force the transition, resulting in cubic runtime.

Time Complexity: \mathcal{O}(N^3)

Subtask 3

We can optimize the solution from subtask 2 with a moving pointer and suffix minimum array.

Alternative Solution

We can do forward DP. Let our state be (i, j), where the first (i - 1) buckets are filled and the last bucket has j units filled. We can either pour b_{i - 1} units into the current bucket, and update the state (i, j + b_{i - 1}), or we can fill this bucket with a_i and move on. In the latter case, let r = \left\lceil\frac{c_i - j}{a_i}\right\rceil. Then we update the state (i + 1, r \times b_i).

Time Complexity: \mathcal{O}(N^2)


Comments

There are no comments at the moment.