Guzac - editorial

PROBLEM LINK:

Practice
Contest

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. :slight_smile:

1 Like

The problem says that pi is not greater than 10^9. But in actual Sequence pi is greater than 10^9. I think this is wrong statement. where pi is the number of candies given to the students.
It is not mentioned anywhere that 0 < i <= k.
so 0 < i <= n is also valid.

Tried the question with the brute force approach and succeeded .But i not quite getting the approach written here and didn’t all the 3 codes provided here.Can someone simplify the approach written here.

Complexity is O(T*KlogK) …Sorting…

2 Likes

Added Fictitious element should be A[0]+X and not A[0]+X+1. Also in the given problem to maximize the S there can be possibility that solution does not exist it will be when A[0]+X < N in this case you will only have N A[0]+X elements to keep in the final array.

ex:

7 3 5
1 2 3

maximum element in the ans array will be 6 but we don’t have 3 elements less than 6 other than 1 2 and 3

The aim og adding fictitious element depend upon the implementation.

Yes min+X can also be used.

See editorialist solution. I first add all K elements. That’s why i use exclusive bounds in my solution. See editorialist solution.

Corrected.

Aim is simple. We have K elements. Select N-K more elements such that sum is maximized. But cannot select elements such that absolute difference is greater than X. So, we start from min+x, the maximum element which can be included, and check each number smaller tham it in reverse order, till we find N-K elements. Since n is upto 1e9 , we need to process multiple elements in a range simultaneously, as explained above.

My solution is getting RUNTIME ERROR can some one tell me the mistake https://www.codechef.com/viewsolution/19799361

@tarzan_1407 can you please tell why my solution is getting RUNTIME ERROR(sigsegv).

The editorial says that the maximum value possible can be A[0] + X but the constraints says that pi<=1e9 and what if A[0] + X > 1e9, then we need to reduce the minimum value in order to satisfy the constraints. Correct me if I am wrong !

In the question it was mentioned that Pi is <=10^9 for all valid i. Now by “valid i”,I thought that i is in the range of 1 to N, but it seems that it was only for first K elements and remaining numbers could be greater than 10^9. My solution got rejected just because of this ambiguity :frowning:

Tricky case :
1
10 3 49
1 43 44

Output:
415

Solution link : https://www.codechef.com/viewsolution/19807822

My approach :

  1. find the maximum P a = Smallest + x = 50
  2. find the required no of positions to be filled = k - n = 7
  3. find the smallest b of the continuous integers you need to find in the formula. b = 50 - (n-1-k) = 50 - (10 - 1 - 3) = 50 - 6 = 45.
  4. That is , for remaining 7 elements , you needed sum of
    A[0…2] + 50 + 49+ 48 + 47 + 46 + 45 + 44.
  5. now since , this (44) was already present in A[k]s , instead of 44 , you can take 43…but is 43 is also present…take 42.
  6. now we can find tot = Sum(A[k]s) + Sum(a…b)
2 Likes

Inconvenience is regretted.

There was a confusion.

We intended the constraint on pi to apply only on first K elements, which are given in input. Remaining elements can be greater than 1e9.

What is the formula for summation over a range?

can anyone give me a test case in which my solution is not working ?
It’s passing in all the test cases given here and sample test cases.
here’s my solution getting WA.
https://www.codechef.com/viewsolution/19811696

Let Function f(N) be Sum of first N natural numbers is given by (N+1)*N/2. For a range [L, R] (Both L and R inclusive), sum of range is f® - f(L-1).

Please explain how to process multiple elements in a range simultaneously. I am not getting.

Consider test case

9 3 10

1 5 10

In this, first add (1+5+10) to answer. Then, add an element min+x+1 = 12 to array and sort it.

Array looks like 1 5 10 12. This means that we can include N-k = 6 elements {11}, {9,8,7,6}, {4,3,2}. Now, see that ideal strategy is to include largest numbers.

After adding 11 to sum, since we know that (5, 10) contains 4 elements while we need 5 elements, we add whole range. 6+7+8+9 = f(9) - f(5), f(n) denotes sum of first n natural numbers.