×

# GUZAC - EDITORIAL

Setter: Aleksa Plavsic
Tester: Hussain
Editorialist: Taranpreet Singh

Easy

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:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

3.9k2892
accept rate: 22%

 2 Complexity is O(T*KlogK) ..Sorting.. answered 20 Aug '18, 02:56 21●1 accept rate: 0% Corrected. (20 Aug '18, 12:06)
 2 Tricky case : 1 10 3 49 1 43 44 Output: 415 Solution link : https://www.codechef.com/viewsolution/19807822 My approach : find the maximum P a = Smallest + x = 50 find the required no of positions to be filled = k - n = 7 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. That is , for remaining 7 elements , you needed sum of A[0..2] + 50 + 49+ 48 + 47 + 46 + 45 + 44. 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. now we can find tot = Sum(A[k]s) + Sum(a....b) answered 20 Aug '18, 19:22 4★niteshx2 41●4 accept rate: 0%
 0 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. answered 20 Aug '18, 01:05 11●2 accept rate: 0%
 0 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. answered 20 Aug '18, 02:16 1 accept rate: 0% 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. (20 Aug '18, 12:10)
 0 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 answered 20 Aug '18, 08:02 127●1●8 accept rate: 0% 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. (20 Aug '18, 12:04)
 0 My solution is getting RUNTIME ERROR can some one tell me the mistake https://www.codechef.com/viewsolution/19799361 answered 20 Aug '18, 12:16 2★honey11 1●1 accept rate: 0% @tarzan_1407 can you please tell why my solution is getting RUNTIME ERROR(sigsegv). (20 Aug '18, 12:35) honey112★
 0 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 ! answered 20 Aug '18, 19:16 21●1 accept rate: 0% 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. (20 Aug '18, 20:25)
 0 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 :-( answered 20 Aug '18, 19:17 1 accept rate: 0% Inconvenience is regretted. (20 Aug '18, 20:25)
 0 What is the formula for summation over a range? answered 20 Aug '18, 22:25 43●5 accept rate: 0% 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(R) - f(L-1). (21 Aug '18, 00:21)
 0 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 answered 21 Aug '18, 00:03 1●1 accept rate: 0%
 0 Please explain how to process multiple elements in a range simultaneously. I am not getting. answered 21 Aug '18, 16:11 73●7 accept rate: 4% 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. (21 Aug '18, 16:31) It means For a range [L, R] (Both L and R inclusive), sum of range is f(R-1) - f(L) ? Anyone, please clear my doubt . (21 Aug '18, 16:57) It means, for a range [L,R] (Both L and R EXCLUSIVE) sum of range is f(R-1) - f(L). We don't include elements in array, since we already added them to sum in first step. (21 Aug '18, 17:31)
 0 Can anyone help me to rectify where my program is failing Solution Link-https://www.codechef.com/viewsolution/19815789 answered 21 Aug '18, 18:47 73●7 accept rate: 4%
 0 [24, 146] N=371 k=2 x=237 what should be output ? There is a mistake in constraints x must be greater than N otherwise There won't be any case possible where all are distinct and still difference between maximum and minimum does not exceed. ( I strongly believe the tester has added that cases otherwise my codes is giving correct for every valid input). Here is the code :- https://www.codechef.com/viewsolution/19811696 link This answer is marked "community wiki". answered 21 Aug '18, 19:14 1●1 accept rate: 0%
 0 hey i did it with same strategy but it is running out of time(TLE), i have checked it thoroughly, please somebody look into it https://ide.codingblocks.com/#/s/21991 (commented code) , https://www.codechef.com/viewsolution/19797503(submission).. if have any test cases please give them answered 22 Aug '18, 19:23 40●2 accept rate: 0%
 0 what if the test case is .. 4 2 4 1e9-2,1e9-2 in that case number might be greater than 1e9 which is the contradiction of the given constraints ?? answered 23 Aug '18, 12:09 1 accept rate: 0% It was intended that the constraint on maximum value to be applicable on first K items only. (25 Aug '18, 18:46)
 0 i dont know why i am getting wrong answer ,i checked with all test cases help me @taran_1407 enter code here#include using namespace std; int main() { int t,n,k,x,i; long long int sum,mi,req,maxval; cin>>t; while(t--) { sum=0; mi=INT_MAX; cin>>n>>k>>x; vectorv; long long int a[k]; for(i=0;i>a[i]; sum+=a[i]; v.push_back(a[i]); mi=min(mi,a[i]); } maxval=mi+x; sort(v.rbegin(),v.rend());  req=n-k; if(maxval-v[0]<=req) { req-=(maxval-v[0]); sum+=((maxval-v[0])*(maxval+v[0]+1))/2;  } else if(maxval-v[0]>req) { sum+=((req)*(maxval+maxval-req+1))/2; req=0; } for(i=0;i0;i++) { if(v[i]-v[i+1]-1<=req) { req-=(v[i]-v[i+1]-1); sum+=((v[i]-v[i+1]-1)*(v[i]+v[i+1]))/2; } else if(v[i]-v[i+1]-1>req) { sum+=((req)*(v[i]-1+v[i]-req))/2; req=0; } } cout<
 0 Entertain the possibility that the minimum number can be some number less than minimum of the pi's; Test Case - 1 13 4 10 4 5 9 13 answered 25 Aug '18, 17:01 1 accept rate: 0% If we go for having a number smaller than minimum of the pi's, even then, it would voilate the maximum difference constraint. But the problem statement Guarantee that a valid sequence always exist, which means that this case cannot appear in test cases. (25 Aug '18, 18:45)
 0 Please anyone take a look at my code and tell me where am I doing it wrong? ll t;scanf("%lld",&t); while(t--) { ll n,k,x;scanf("%lld %lld %lld",&n,&k,&x); ll a[k+1]; ll s=0,cou=k; f(k) { scanf("%lld",&a[i]); s+=a[i]; } sort(a,a+k); a[k]=a[0]+x+1; repb(i,k,1) { if(a[i]-a[i-1]>1) { if((cou+a[i]-1-a[i-1])<=n) { s+=(a[i]*(a[i]-1))/2; s-=(a[i-1]*(a[i-1]+1))/2; cou+=a[i]-a[i-1]-1; } else { s+=(a[i]*(a[i]-1))/2; ll need=n-cou; need=a[i]-1-need; s-=(need*(need+1))/2; } } } printf("%lld\n",s); }  answered 09 Sep '18, 17:52 4★amstan 11●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,677
×1,000
×877
×649
×555
×80

question asked: 18 Aug '18, 14:21

question was seen: 1,959 times

last updated: 25 Aug '18, 18:46