PREREQUISITES -
Sorting, Binary Searching, Sliding Window
QUICK EXPLANATION -
Sort the lengths array. For each query K, binary search for the largest element smaller than K and name it cur. Then binary search again on the prefix difference sum array (which will give the number of snakes to be fed to snakes in [prev+1, cur] to make their length at least K) in the region [1, cur] for finding the least index of snake to be killed and let it be prev. The answer is N-prev.
EXPLANATION -
Some key observations before we jump to the solution -
-
The most optimal choice would be to feed the largest snakes shorter than K[i] on the smallest snakes and to not feed the snakes greater than K[i] in length in i^{th} query.
-
If we get some X smallest snakes killed for some query K[i], then, for all queries where K[j] > K[i] for some j, we get Y smallest snakes killed where the condition (Y \geq X) will be satisfied.
There are many solutions to this problem some of which are discussed below -
ONLINE SOLUTION -
Let us sort the lengths array as the order doesn’t matter for the answer.
Let us solve the problem for a query having its value as K. The most naive solution would be to keep iterating forward from 1 till we reach an element just smaller than K and name this index as cur. Let us keep one more pointer/variable prev which denotes the number of smallest snakes eaten, initially at 0. We will start feeding from cur^{th} snake. Now, to make it of length K, we need to feed it on (K-l[i]) smallest snakes available, where i is initially cur. We increase the prev by (K - l[i]) and decrease i by 1 to reflect this change. We do this process of increasing prev and decreasing i while the condition (i > prev) remains satisfied. Then we print the answer to be simply N - i - 1.
Complexity - O(Q*N)
This solution is inefficient but can be passed in TL if we optimise the solution by binary searching the cur and prev as both functions are monotonic in nature.
Now, let us also make a prefix sum array defined as follows -
**
**
For every query having value K, we first find the value of cur by binary searching on length array as it is in increasing order. Then, we also find the largest index prev which is going to get killed. In the naive solution also, we were taking the summation of (K - l[i]) from cur by iterating backwards and set the prev equal to that summation and it can be observed that the function (i > prev) is monotonic as i is decreasing and prev increasing.
prev can be found simply by binary searching method on sample space [1, cur]. Binary searching method works because we are finding the smallest j for which the condition
**
**
is satisfied and this function is monotonic with increasing j and then we set prev = j. We want the shortest j as this is the demand of the question to minimize the snakes being eaten OR maximize the snakes of length \geq K which is (N - j).
The need for the presum array is that it is the number of snakes required to be killed to make the length of snakes in [prev+1, cur] to be more than or equal to K and which is the demand of the question to maximize the number of snakes of length K.
After finding prev, answer is (N - prev) for the query having value K.
Complexity - O((N+Q)*log(N))
OFFLINE SOLUTION -
Let us again sort the length array in increasing order as the order doesn’t matter. Also, let us sort the queries array along with their indices in increasing order of K values.
Hence, a 2-pointer offline solution will be to maintain 3 variables - cur, prev, prefix - where cur means that cur^{th} element is the largest element smaller than K value of current query which we are processing. prev refers to the largest index smaller than cur which is killed and can also be said that prev smallest snakes will be killed. Another thing to observe is that cur and prev can only increase if the queries are sorted according to K value of queries according to observation 2.
Let us assume that currently we are processing answer for j^{th} query in sorted order. prefix refers to
To calculate prefix, we keep on increasing cur and update prefix by adding (K[j] - l[cur]) to prefix till we get l[cur+1] to be greater than K[j]. Then, We keep on increasing prev and keep updating prefix by subtracting (K[j] - l[prev]) while (prefix > prev). Then we get the answer for that query to be simply (N - prev) as prev refers to the largest index of snake which will be killed. Before proceeding to the next query, we also update the prefix by adding
[(cur -
prev) * (K[j+1] - K[j])]. The need for the prefix is that it is the number of snakes required to be killed to make the length of snakes in [prev+1, cur] to be exactly equal to K[j] and which is the demand of the question to maximize the number of snakes of length K[j].
Remember, that we sorted the query and length arrays both in increasing order.
Complexity - O(N*log(N) + Q*log(Q))
There also exists another solution which is to do the naive solution as explained above, but to not do computation again for some K previously encountered. This can be implemented easily by mapping K value of query to its answer and checking everytime before computing answer for a query, that if the answer for same K value has been computed before using a BST (map or set in C++). It can be proved easily that it is also efficient.
Offline solution implementation - here
And yes, if your code got the value of K and immediately printed its answer, before getting the next K value , it was an online solution!