### atlasworld's blog

By atlasworld, history, 7 months ago, ,

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 .

> < > < >

• -3

 » 7 months ago, # | ← Rev. 3 →   +8 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: min_last_k[i] = min(min_last_k[i], a[(i-k+n) % n]; 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.
•  » » 7 months ago, # ^ |   0 Thanks MSchallenkamp for help . i understood ur approach