You are not logged in. Please login at www.codechef.com to post your questions!

×

GUZAC - EDITORIAL

1
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. :)

This question is marked "community wiki".

asked 18 Aug '18, 14:21

taran_1407's gravatar image

6★taran_1407
4.0k31103
accept rate: 22%

edited 20 Aug '18, 12:07


Complexity is O(T*KlogK) ..Sorting..

link

answered 20 Aug '18, 02:56

sauravtygg's gravatar image

3★sauravtygg
211
accept rate: 0%

Corrected.

(20 Aug '18, 12:06) taran_14076★

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)
link

answered 20 Aug '18, 19:22

niteshx2's gravatar image

4★niteshx2
414
accept rate: 0%

edited 20 Aug '18, 19:24

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.

link

answered 20 Aug '18, 01:05

decentgeek's gravatar image

1★decentgeek
112
accept rate: 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.

link

answered 20 Aug '18, 02:16

pawan1210's gravatar image

1★pawan1210
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) taran_14076★

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

link

answered 20 Aug '18, 08:02

byomkeshbakshy's gravatar image

5★byomkeshbakshy
12719
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) taran_14076★

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

link

answered 20 Aug '18, 12:16

honey11's gravatar image

2★honey11
11
accept rate: 0%

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

(20 Aug '18, 12:35) honey112★

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 !

link

answered 20 Aug '18, 19:16

tushar1252's gravatar image

4★tushar1252
211
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) taran_14076★

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 :-(

link

answered 20 Aug '18, 19:17

debadri1010's gravatar image

4★debadri1010
1
accept rate: 0%

Inconvenience is regretted.

(20 Aug '18, 20:25) taran_14076★

What is the formula for summation over a range?

link

answered 20 Aug '18, 22:25

strawhatdragon's gravatar image

2★strawhatdragon
435
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) taran_14076★

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

link

answered 21 Aug '18, 00:03

snjumaheshwari's gravatar image

4★snjumaheshwari
11
accept rate: 0%

edited 21 Aug '18, 00:04

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

link

answered 21 Aug '18, 16:11

osho_garg's gravatar image

2★osho_garg
737
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) taran_14076★

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) osho_garg2★

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) taran_14076★

Can anyone help me to rectify where my program is failing Solution Link-https://www.codechef.com/viewsolution/19815789

link

answered 21 Aug '18, 18:47

osho_garg's gravatar image

2★osho_garg
737
accept rate: 4%

edited 21 Aug '18, 18:57

[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

snjumaheshwari's gravatar image

4★snjumaheshwari
11
accept rate: 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

link

answered 22 Aug '18, 19:23

arjun_9426's gravatar image

5★arjun_9426
402
accept rate: 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 ??

link

answered 23 Aug '18, 12:09

cap_coder's gravatar image

2★cap_coder
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) taran_14076★

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;

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;i<v.size()-1&&req>0;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<<sum<<"\n";

} }

link

answered 24 Aug '18, 23:20

ajaysaundeep's gravatar image

3★ajaysaundeep
01
accept rate: 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

link

answered 25 Aug '18, 17:01

forbcode1's gravatar image

3★forbcode1
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) taran_14076★

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

answered 09 Sep '18, 17:52

amstan's gravatar image

4★amstan
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,851
×1,024
×890
×721
×558
×80

question asked: 18 Aug '18, 14:21

question was seen: 2,034 times

last updated: 25 Aug '18, 18:46