Problem Link - Parchment
Problem Statement
On a mysterious island, you find an old parchment. Written on it are N integers, each in the range [1,A]. You quickly deduce that this parchment is the root of all evil, and therefore you decide to destroy it. To destroy it, you need to simply delete every number on the parchment.
Fortunately for you, lying next to the parchment is a strange device. You do some research and realise that you can power this device up to any non-negative integer value K. After that, you can use the device. Each time you use the device, you will choose some non-negative integer value X, and every number on the parchment which is in the range [X,X+K] will immediately be deleted. Notice that the value K is chosen once at the start and then fixed for all uses of the device.
You realise that the device is very old, and so you don’t actually know how many times you can use the device before it will stop working. You also don’t want to use the device on a higher power level than you need to, since that is also likely to make the device break faster. Hence you wonder, if you could use the device at most F times, what is the minimum power level for which it would be possible for you to delete every number on the parchment?
You want to find the answer for Q different values of F, denoted F[1] ,F[2]…F[Q].
Approach
The key idea is to minimize the power level K for a given number of uses F of the device. To solve this, we first need to sort the array of numbers in increasing order. Then, for each possible K (from 0 to A + 1), we calculate the minimum number of uses required to delete all the numbers. The process of deleting involves starting from the smallest number and covering as many numbers as possible with each use of the device, i.e., every time we choose a number X from the array, we mark all numbers in the range [X, X + K] as deleted.
Once we have the minimum number of uses needed for each possible K, we use binary search to efficiently find the smallest K for each query F such that the device can clear all the numbers using F or fewer uses. We precompute the number of uses for all possible K values to allow for fast queries. For each query, we search over the precomputed values to find the optimal K.
Time Complexity
Sorting the array takes O(N log N). The binary search for each query has a complexity of O(log(A)), and checking the number of uses for each K is O(N). Overall complexity is O(N log N + Q \times log(A)).
Space Complexity
The space required is O(N + A) for storing the array and precomputed values.