Editorial for Coconut Canopy

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Each tree at position $n_i$ ~n_i~ drops coconuts into the two neighboring positions $n_i - 1$ ~n_i - 1~ and $n_i + 1$ ~n_i + 1~. We can therefore compute, for every street position, how many coconuts would land there if we placed a basket on that slot. Now, we only need the to sum the values of the top $k$ ~k~ locations. Sorting the values in descending order and summing the largest $k$ ~k~ entries (or all of them if $k > n$ ~k > n~) maximizes the overnight harvest.

Building the counts takes $O(n + m)$ ~O(n + m)~ and the sort dominates with $O(n \log n)$ ~O(n \log n)~.

A linear-time solution is also possible.

Solution (Python)

n,m,k = map(int,input().split())
locs= list(map(int,input().split()))

cocs = [0 for i in range(n)]
for i in locs:
    loc = i-1
    if(0 <= loc-1 < len(cocs)):
        cocs[loc-1] += 1

    if(0 <= loc+1 < len(cocs)):
        cocs[loc+1] +=1

cocs.sort(reverse=True)

i = 0
ans = 0
while (i < k and i < len(cocs)):
    ans += cocs[i]
    i+= 1

print(ans)

Comments

There are no comments at the moment.