Editorial for Riolku's Mock CCC S4 - Clumsy Cindy
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
This subtask was intended to reward brute force solutions.
Time Complexity:
Subtask 2
There are many possible DP solutions to the problem, but we'll only expand on one here.
Let be the minimum number of fill operations needed to fill the first
buckets such that the fill operation was used on bucket
exactly
times. For this subtask, we can brute force the transition, resulting in cubic runtime.
Time Complexity:
Subtask 3
We can optimize the solution from subtask with a moving pointer and suffix minimum array.
Alternative Solution
We can do forward DP. Let our state be , where the first
buckets are filled and the last bucket has
units filled. We can either pour
units into the current bucket, and update the state
, or we can fill this bucket with
and move on. In the latter case, let
. Then we update the state
.
Time Complexity:
Comments