PROBLEM LINK:
Author and Editorialist: Soumik Sarkar
Tester: Sarthak Manna
DIFFICULTY:
EASY
PREREQUISITES:
Sorted set/Priority queue/Heap, Difference array
PROBLEM:
There is an array Z of size N denoting the health of N zombies. There also M types of beams of the form (L, R, K) where K denotes the number of times the beam can be used to decrease every element in Z[L..R] by 1. Find the minimum number of beam drops needed to reduce all elements in Z to 0 or determine if it is impossible.
EXPLANATION:
Consider the first zombie Z[1]. This zombie can only be affected by beams whose L = 1. Let’s gather all such beams into a set U. If we want to reduce Z[1] to 0, we have to drop some beams from U. Of course we should drop the number of beams exactly equal to its health and not waste any beams. The question is… which beams should we drop?
Here it makes sense to make a greedy choice and drop the beams from U with largest R. That way we are affecting maximum zombies to the right of L at the same time.
After killing the first zombie let us move to Z[2]. Of course Z[2] may already have been reduced to 0 after being affected by the beams that we used on Z[1], but let us assume it is still non-zero. Now we are faced with a similar situation as before. Only those beams with L \le 2 can affect Z[2]. But all beams with L = 1 were added to U, and some of them are even already used. So we must add all the beams that have L=2 to the leftover beams in U, and make greedy choices again to reduce Z[2].
Generalizing, the solution involves maintaining an active set of beams U. At any index i, all beams that can affect i, ie. beams that have L \le i, are either in set U or have been used up. To kill zombie i, only as many beams as required are used, the beams with largest R being used first. The process is carried out for i = 1 to N.
The algorithm can be described as follows:
U = empty set
ans = 0
for i in [1..N]:
add all beams with L = i to U
while Z[i] > 0:
let b be the beam with largest R from U
if U is empty or b.R < i:
zombie i cannot be killed
exit loop
if b.K > Z[i]:
ans = ans + Z[i]
b.K = b.K - Z[i]
reduce every element in Z[i..b.R] by Z[i]
else:
ans = ans + b.K
Z[i] = Z[i] - b.K
reduce every element in Z[i..b.R] by b.K
remove b from U
The above strategy is optimal, but how can we implement it efficiently?
The two procedures that are non-trivial are retrieving the update with largest R from U and applying decrement operations on a range Z[L..R].
For the first we can maintain U as a sorted set or a priority queue. This allows retrieval of largest element in \mathcal{O}(\log N) time. Most languages have implementations of these structures in the standard library.
For the second the simplest solution is to use a difference array D. Generally speaking, to apply an update on [L..R] we perform D[L] += X and D[R + 1] -= X and then get the original array using prefix sums. Here we need to apply the updates as we go along. Note that the updates to be applied only affect elements to the right of the current index, so we can maintain the prefix sum in a variable and just modify D[R + 1]as required.
The complexity of the solution is \mathcal{O}((N + M)\log M).
AUTHOR’S AND TESTER’S SOLUTION:
Author’s solution can be found here
Tester’s solution can be found here.
