atlasworld's blog

By atlasworld, history, 6 years ago, In English

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 .

> < > < >

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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.