DSTROY IUPC Editorial

editorial
, ,
1

PROBLEM LINK:

DSTROY - Destroy the asteroids IUPC-Plinth’20
Author - priyam2k
Editorialist - Priyam Khandelwal

DIFFICULTY:

Medium

PREREQUISITES:

Binary Search

PROBLEM:

Let an operation be to reduce exactly K elements in an array by one. Find out how many such operations are possible.

Explanation

We will use binary search on the number of minutes this operation can be done. Now how to check, if mid minutes is possible? If an element is more than mid we can reduce it mid times (add mid to sum) and if an element is less than mid (let the value of this element be x) then we can reduce this element x times (add x to sum. So when we add these numbers we will get how many operations can be done if the condition was K=1. For an arbitary K we will just have to check if \frac{sum}{mid} \geq K. If this equality holds then we can do this operation for mid minutes otherwise we can’t. The implementation is straightforward.

Author solution

Author’s Solution

4 Likes
2

Please prove the claim for general K. It is obvious for K = 1. I’ve seen this appear at several places but I haven’t seen a proper proof anywhere. Coz of this I have to rely entirely on intuition wherever a sub-problem like this appears. I’d like to see a proof of this. How can one prove that for all K checking sum/mid >= K is sufficient ?

Also if you have some problems based on similar ideas, (i.e. proving some greedy looking idea or some set of conditions which are obviously necessary but turn out to be sufficient too) in conjugation with binary search that will be nice. I recently found out of wqs binary search on CF which is also another smart binary search idea. I amazes me how much I don’t know about binary search!

EDIT : I came up with a proof, so lite. I’d still like to get some problems based on above mentioned ideas, solving them will be fun.

6 Likes
3

@megatron10 Can you share the proof here?

4

Can someone explain why this last s/m check works

1 Like
5

Can you share the proof here? @megatron10

6

Ok so we can easily think of it as -
consider we choose M minutes as ans - Now we need to verify if its correct.
Now consider an array having elements
[a, b, c, d , M, M, M, M]
a, b, c, d<M
the four M’s gives us min k =4.
And now (a+b+c+d)/M will give us the remaining k because we can clutter them and make them just a little big than M. Then they will contribute these many k’s.

8 Likes