GUZAC - EDITORIAL

editorial
, , , , ,
1

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
2

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.

3

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.

4

Complexity is O(T*KlogK) …Sorting…

2 Likes
5

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

6

My solution is getting RUNTIME ERROR can some one tell me the mistake CodeChef: Practical coding for everyone

7

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 !

8

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:

9

Tricky case :
1
10 3 49
1 43 44

Output:
415

Solution link : CodeChef: Practical coding for everyone

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
10

What is the formula for summation over a range?

11

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

12

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

13

Can anyone help me to rectify where my program is failing
Solution Link-CodeChef: Practical coding for everyone

14

[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 :- CodeChef: Practical coding for everyone

15

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 Coding Blocks IDE (commented code) , https://www.codechef.com/viewsolution/19797503(submission)… if have any test cases please give them

16

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 ??

17

i dont know why i am getting wrong answer ,i checked with all test cases help me @taran_1407
link text

18

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

19

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);
}
20

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.