DREAM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, Heaps

PROBLEM:

There are N numbers written in an array, ith being f(i). You can choose a segment of array of length K and the minimum number of that segment which is still present will be erased (creating a hole at that location). If there are multiple numbers which are equal to the minimum, all of them are erased. What is the minimum number of times, one must do this operation to erase all the numbers.

QUICK EXPLANATION:

You can always try to erase the smallest number first. After choosing which number to erase, interval can be chosen greedily to erase maximum numbers at one go.

DETAILED EXPLANATION:

We prove following three very intuitive claims :

  1. There is some optimal solution in which first dish to be cooked is the one
    having smallest f(i) value.
  2. In each turn we could be greedy and cook meal having the smallest f(i) value.
  3. Once a meal to be cooked has been chosen, interval can be chosen greedily.

  • Let’s prove claim 1 :
    Assume that dish p is the one having least value of f(i). Assume that in optimal
    solution, first meal cooked is not the one having smallest f(i) time. Let’s
    look at the windows chosen [i1, i1+K-1), [i2, i2+K), [i3, i3+K) … . One of these contains p, say rth is the first window that contains p. If you swap it with a window before it, nothing changes since all the dishes that were cooked
    in these two windows would be cooked after the swap as well. By swapping again
    and again you can bring it at the front and cost of your solution won’t increase.
    Hence we’ve produced another optimal solution in which dish with smallest cooking
    time is cooked first. Hence proved :slight_smile:

  • Claim 2 follows from claim 1 naturally, by applying this same argument again and
    again after each erase operation.

  • For proving claim 3, let’s say the smallest cooking time is T and there are K
    different meals having this time. By claim 2 above, it is clear that in first few
    rounds we would cook all these dishes until they’re all cooked. Now say these
    dishes from left to right are d1, d2 … dk. Here it is easy to see that we can
    chose intervals greedily i.e fix up an interval with left end at d1 and try to
    cook as many dishes as possible in one go only. Then put left end of our
    interval on next uncooked dish and so on.

SETTER’S SOLUTION:

Can be found here.
Setter noted that all dishes having same cooking time can be processed together (spread over a few rounds) and so we don’t need to sort the elements either on cooking time. His algorithm in his own words:

Cook first uncooked meal with least
index from entire array and let’s the
index of this meal is I. then cook
all the meals i which is
I<=i<=I+K and have f(i)=f(I). Repeat this procedure until all meals
are cooked.

TESTER’S SOLUTION:

Can be found here.

4 Likes
2

We need to cook the meal with least cooking time first. So how come algorithm of setter is right.?

3

In setter’s solution as well, first dish to be cooked would be the one having lowest f(i) value. However they don’t need to be processed in that order - from the editorial above, we can see that dishes having same f(i) value are processed together.

4

Tester’s and setter’s solutions are the same.

5

Could anyone explain the use of heaps here ?

6

well, instead of sorting you can push all element on heap (minHeap, so on the top will be the element with smallest f(i) and smallest position among elements with that smallest f(i)) and after all elements are on heap, just pop them out in order, solution is almost same as testers, just you will push and pop from the heap, instead adding in array, sorting, and reading from sorted array. I hope i helped you.

7

This can be solved very easily with the use of map
Here is my code:-

#include <bits/stdc++.h>
using namespace std;
int main()
 {
    ios_base::sync_with_stdio(0);
    map<long,vector<int> > M;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
      {
        long k;
        cin>>k;
        M[k].push_back(i);
     }
    map<long,vector<int> >::iterator it=M.begin();
    long ans=0;
    while(it!=M.end())
     { 
        vector<int> v=it->second;
        int s=v[0];
        ans++;
        for(int i=1;i<v.size();i++)
          {
               if(v[i]-s+1>k)
                {
                   s=v[i];
                   ans++;
               }
         }
        it++;
    }
    cout<<ans;
}
8

Fixed formatting of the code. :slight_smile: