DPF - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

There are N flowers in a garden, initially all in bloom.
The i-th flower will regrow after T_i days if plucked.

For each of D days, Chef will pluck some flowers from the garden.
What’s the maximum total number of flowers that can be plucked, while ensuring that there are always at least K flowers in bloom?

EXPLANATION:

The main idea here is to simply be as greedy as possible: whenever it’s possible to pluck a flower without breaking the K condition, do so; and if there are multiple choices for which flower to pluck, choose the ones that regrow the fastest.

This leads to a simple simulation.
For each of the D days,

  • Make a list of all available flowers.
    To do this, you’ll need to know the last time when each flower was plucked.
    Store an array \text{last\_plucked}[i] which denotes the last time flower i was plucked; then flower i is available on the current day (say x) if and only if \text{last\_plucked}[i] + T_i \leq x.
  • Sort this list in ascending order of their regrow time, i.e. T_i values.
  • Then, take as many flowers as you can in this ascending order, while ensuring that K flowers still remain.
  • Make sure to update the value of \text{last\_plucked}[i] for all the flowers that you do pluck.

To avoid having to sort for every day, you can also just sort the flowers once at the very beginning and use this sorted order (while skipping unavailable flowers).

TIME COMPLEXITY:

\mathcal{O}(DN\log N) or \mathcal{O}(N\log N + DN) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k, d = map(int, input().split())
    t = list(map(int, input().split()))
    t.sort()
    
    last = [-100]*n
    ans = 0
    for day in range(d):
        available = 0
        for i in range(n):
            if day >= last[i] + t[i]:
                available += 1
        
        pluck = available - k
        for i in range(n):
            if day >= last[i] + t[i] and pluck > 0:
                ans += 1
                pluck -= 1
                last[i] = day
    print(ans)
2

why not just sort the array once and then go for counting number of times each of the top n-k flowers can be picked in the given number of days the time complexity would be O(NlogN + N) instead of O(NlogN + DN)

3

I think there has to be a dlogn solution using priorityQueue , I tried not sure where it went wrong.

  PriorityQueue < int[] > bloom = new PriorityQueue<>((a , b)->(a[0] == b[0]) ? arr[a[1]] - arr[b[1]] : a[0]  - b[0]);
		    PriorityQueue < int[] > notbloom = new PriorityQueue<>((a , b)->(a[0] == b[0]) ? arr[a[1]] - arr[b[1]] : a[0]  - b[0]);

		    for (int i =0 ;i < n ; i++){
		        bloom.offer(new int[]{1 , i});
		    }
		    
		    int cnt = 0;
		    for (int i = 1 ; i<=d ; i++){
		        while(notbloom.size() > 0 && notbloom.peek()[0] <=i)
		            bloom.offer(notbloom.poll());
		        while(bloom.size() > k){
		            cnt = cnt + 1;
		            int[] f = bloom.poll();
		            f[0]=i + arr[f[1]];
		            notbloom.offer(f);
		        //    System.out.println(f[0] + " " + f[1] + " " + i);
		        }
		    }
		    System.out.println(cnt);
4

@iceknight1093 , please have a look into the above

5

Its great idea.

6

@iceknight1093 Is there any proof for the greedy idea given in editorial ?

7

You are using greedy. The bloom should always be giving you, among currently blooming flowers, the one with the smallest regrowth T[i].

PriorityQueue<int[]> bloom = new PriorityQueue<>(
    (a,b) -> arr[a[1]] - arr[b[1]]
);

PriorityQueue<int[]> notbloom = new PriorityQueue<>(
    (a,b) -> a[0] - b[0]
);
1 Like
8

awesome , i was getting confused that flower which bloomed early should get plucked , but didn’t consider the growth factor.
Thank you sir.