PROBLEM LINK:
Setter: Aleksa Plavsic
Tester: Hussain
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Math, Greedy
PROBLEM:
Given N, number of elements on sequence P, and first K elements and Maximum difference between Maximum and minimum element of sequence P, find the maximum possible sum of this sequence. All elements of P should be unique.
QUICK EXPLANATION
-
Find minimum element in first $K$ elements. Maximum difference $X$ implies that Maximum element of this sequence can be at most $min+X$. -
We can greedily choose values from $min+X$ to $min$ not already in $P$, choosing larger values first so as to maximize sum. -
After choosing $N-K$ new elements, our $P$ contains $N$ elements, and sum of all these elements is answer. -
Checking every single number will take at least $N-K$ iterations which will time out. So, we will add multiple numbers simultaneously.
EXPLANATION
First of all, we can add all these K elements to an array and sort them. Minimum element is A[0]. Since maximum difference between smallest and largest element is X, so, Maximum element should be A[0]+X. It does not make sense to choose a number < A[0] as this would reduce the maximum choosable element, reducing the final sum.
Now, Brute force solution is to check every element from A[0]+X to A[0] will we find N-K more elements, adding the element if it doesn not already exist in P. This solution has complexity of order O(N) which will Time out.
Now, to get solution of order O(K), see that consecutive pair of elements each represent a range of elements not yet chosen.
If A[i]-A[i-1]>1 for every 2 \leq i \leq K , we can choose any number in range [A[i-1]+1, A[i]-1]. Using the formula for summation over range of numbers, we can add all these elements at once in O(1), reducing overall time complexity to O(K).
Boundary case need to be handled separately. It occurs when A[K-1] < A[0]+X.
4 2 4
1 4
In above case, we can choose 3rd element as 5 and 4th element as 3.
To handle this, we can simply add fictitious element A[0]+X+1 at end of sequence (Remember not to add this to answer.)
So, our final solution looks like
Iterate from right to left, add set of number using the formula. Carefully handle case when Length of segment is more than Number of elements remaining to be added, Say R. In this case, only add largest R numbers in current range.
Have a look at solutions below if any doubt, and feel free to ask in comments.
Complexity:
Time complexity of this solution is O(T*K*logK).
Similar problem
Minimize sum instead of maximize. Same constraints. But, it is not guaranteed that solution always exist.
Also, Find conditions when solution doesn’t exist.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
