IN the problem colorful slimes you have to pick all color in minimum moves ,
Its mentioned in the editorial for a particular color i we need
min{a[i] , a[i-1] , ... , a[i-k]} . i dont understand how author uses this condition . and should we iterate for each k and then each i or for each i and the each k . how to deal with cycles , that is when we reach last index , how to relate it with first.
Can anyone who solved this problem , share approach .
> < > < >
Let's think about how we're going to make a particular color. We can create this color by catching it directly and applying no spell casts. Alternately, we could commit to doing 1 spell cast total; this means that we can create this color by using a[i] after the cast or a[i-1] before the cast, which we obviously want to minimize. Generally, with k spell casts committed, the time to make color i is min(a[i], a[i-1], ... a[i-k]).
So to solve the problem, lets loop for our k and maintain this min(a[i], a[i-1]...) in an array we can call min_last_k. Whenever we increase our k we need to update this array, so we do a loop to update it using:
Now at each k we can calculate our total score by the sum over min_last_k + (k * the spell time). Lets get the min value for that over all the k as our final answer. This takes total n^2 time (n rounds with n updates each), which should fit within the time limit.