ONEFROMK - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

1307

PREREQUISITES:

Sorting

PROBLEM:

You’re given an array A of length N.
For a fixed K, do the following:

  • Consider the first K elements, pick one out of them and remove it.
  • Insert the (K+1)-th element, then pick one and remove it.
  • Insert the (K+2)-th element, then pick one and remove it.
  • And so on, till the N-th element.

For each 1 \leq K \leq N, find the maximum possible sum of the removed elements, if you choose optimally.

EXPLANATION:

Let’s fix K, and see what the answer should be.

After the entire process is done, there will be K-1 unpicked elements.
Maximizing the sum of the picked elements is equivalent to minimizing the sum of the unpicked elements.
Of course, the absolute best case for us is if the unpicked elements are the smallest K-1 elements of A.

It’s not hard to see that this can always be achieved: whenever we pick from the bucket, it will contain K elements; so we can always pick an element that’s not among the smallest K-1.
So, for a fixed K, the answer is simply the sum of the array, minus the sum of the smallest K-1 elements.

Finding this quickly for every K can be done easily with the help of sorting.
Let’s sort A, so that A_1 \leq A_2 \leq \ldots\leq A_N.
Then, notice that that the answer for K = i is just A_i + A_{i+1} + \ldots + A_N, i.e, the suffix sum of A starting at index i. After all, this is exactly what remains after the smallest i-1 elements are excluded.

So, after sorting A, just compute its suffix sum array and print it: that’s the solution!

TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    ans = sum(a)
    for i in range(n):
        print(ans, end = ' ')
        ans -= a[i]
    print()
2 Likes
2 
> #include<bits/stdc++.h>
> using namespace std;
> void solve(vector<long long >&v,int n){
>     int sum = 0; 
>      for(int i  = 0; i < n;i++){
>       sum += v[i];
>     }
>     for(int i  = 0; i < n;i++){
>       cout<<sum<<" "; 
>       sum -= v[i];
>     }
> }
> int main()
> {
> 
>      int t; 
>      cin >> t; 
>      while(t--){
>         long long int n; 
>         cin >> n; 
>         vector<long long >v; 
>         for(int i = 0; i< n; i++){
>             long long  a; 
>             cin >> a; 
>             v.push_back(a);
>         }
>         sort(v.begin(), v.end());
>         solve(v,n);
>    
>         cout<<endl; 
>      }
> 
>     return 0;
> }
  • List item

MY code is not submited i try to much where i am wrong in this code it passese test case 1 and 3 only tell my why this is happening

3

You just have to use long long int for sum

1 Like
4

ok