You are not logged in. Please login at www.codechef.com to post your questions!

×

CLKLZM - Editorial

PROBLEM LINK:

Practice
Contest

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.

asked 16 Apr, 00:39

meooow's gravatar image

6★meooow ♦
6.3k415
accept rate: 47%

edited 16 Apr, 01:02

nicely explained :)

(18 hours ago) harrypotter03★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×13,920
×3,035
×128
×42
×3

question asked: 16 Apr, 00:39

question was seen: 320 times

last updated: 18 hours ago