PROBLEM LINK:Setter: Aleksa Plavsic 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
EXPLANATIONFirst 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 $NK$ 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[i1]>1$ for every $2 \leq i \leq K$ , we can choose any number in range $[A[i1]+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[K1] < A[0]+X$.
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: 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 18 Aug '18, 14:21

Complexity is O(T*KlogK) ..Sorting.. answered 20 Aug '18, 02:56

Tricky case : 1 10 3 49 1 43 44 Output: 415 Solution link : https://www.codechef.com/viewsolution/19807822 My approach :
answered 20 Aug '18, 19:22

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

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
@tarzan_1407 can you please tell why my solution is getting RUNTIME ERROR(sigsegv).
(20 Aug '18, 12:35)

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

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

Can anyone help me to rectify where my program is failing Solution Linkhttps://www.codechef.com/viewsolution/19815789 answered 21 Aug '18, 18:47

[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

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

i dont know why i am getting wrong answer ,i checked with all test cases help me @taran_1407 enter code here#include<bits stdc++.h=""> 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; vector<int>v; long long int a[k]; for(i=0;i<k;i++) {="" cin="">>a[i]; sum+=a[i]; v.push_back(a[i]); mi=min(mi,a[i]); } maxval=mi+x;
req=nk; if(maxvalv[0]<=req) { req=(maxvalv[0]); sum+=((maxvalv[0])*(maxval+v[0]+1))/2;
} } answered 24 Aug '18, 23:20

Please anyone take a look at my code and tell me where am I doing it wrong?
answered 09 Sep '18, 17:52
