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

×

KSUM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Sergey Kulik
Editorialist: Sunny Aggarwal

DIFFICULTY:

Easy

PREREQUISITES:

Sorting, Greedy, Data Structure, Implementation.

PROBLEM STATEMENT:

Given an array $A$ containing $N$ positive integers and an integer $K$. We are asked to report the largest $K$ values from the list of sums of all possible subarrays of array $A$.

EXPLANATION:

Subtask 1

Listing sums of all the possible subarrays of $A$ and finding the largest $K$ values will be enough to pass this subtask.

C++ Code

#define ll long long
void solve(int N, int K, int *arr) {
    vector<ll> sum;
    for(int i=1;i<=n;i++) {
        long long int s = 0;
        for(int j=i;j<=n;j++) {
            s += arr[j];
            sum.push_back(s);
        }
    }
    sort(sum.rbegin(), sum.rend());
    for(int i=0; i<=K-1; i++) cout << sum[i] << " ";
    cout << "\n";
}

Time Complexity

$O((\frac{N \times (N+1)}{2})) \times \log{\frac{N \times (N+1)}{2}})$

Complete Code Link

Note

Although the above solution will get passed on first subtask but we can have slight better complexity by maintaining a priority queue for the first $K$ elements instead of sorting all the sums.

Complete Code Link

Subtask 2

It is easy to see that the above solution will time out for this subtask.

Then, how to approach it ?

It can be noticed that the largest and first value will always be sum of all the elements as it is given that all elements are positive integers. It means the sum is corresponding to the subarray $[1 to N]$ inclusively. Now, we have taken up the range $1...N$ and we can see that the next possible largest sum will be the maximum of sum of range $2...N$ and range $1...N-1$. Let us assume that the second largest is obtained from the range $1...N-1$. Then, the third largest sum will be maximum of sum of range $2...N$ ( previous range left ), range $2...N-1$ and range $1...N-2$ ( new ranges ). The above procedure can be run $K$ times to find the largest $K$ values.

How to implement above idea ?

Let us maintain a priority queue $S$ ( set can also be used in C++ ). So, whenever we are taking the sum of a range say [L to R] from S, we can simply insert 2 new values to $S$ i.e sum of range $[L+1 to R]$ and $[L to R-1]$ if $L != R$. Note that along with sum of range we are also maintaining the indices i.e $L$ and $R$ denoting that range in our priority queue.

C++ Code

#define ll long long
void solve(int N, int K, int *arr) {
    set<pair<ll,pair<int,int>> S;
    long long int prefix_sum[N+1];
    for(int i=1;i<=n;i++) {
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }

    S.insert({prefix_sum[N], {1, N}});
    while( K -- && !S.empty() ) {
        pair<ll,pair<int,int>> top = *S.begin();
        S.erase( top );
        long long int sum;
        int L, R;
        sum = top.first;
        L = top.second.first;
        R = top.second.second;
        cout << sum <<" ";
        if( L != R ) {
            S.insert({sum-arr[L], {L+1, R}});
            S.insert({sum-arr[R], {L, R-1}});
        }
    }   
} 

TIME COMPLEXITY:

$O(K \times \log{K})$

AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 19 Apr '16, 23:22

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

edited 30 Apr '16, 23:14

admin's gravatar image

0★admin ♦♦
19.8k350498541


Complexity is

O(K x log K) or O(K x log n) ??

Cause the size of the set is maximum n

link

answered 01 May '16, 00:20

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

It's actually O(n + klogk). n for input and prefix sums. And klogk as the while loop runs k times, and each time we insert and delete from the queue once, each having logk complexity.

(01 May '16, 21:14) s1d_35★
link

answered 01 May '16, 02:09

anupam_datta's gravatar image

4★anupam_datta
469630
accept rate: 7%

In editorial there is mistake , S.rbegin() instead of S.begin() .

link

answered 01 May '16, 15:09

shuboy2014's gravatar image

2★shuboy2014
112
accept rate: 0%

edited 01 May '16, 15:11

Guys, writing editorials is hard. It is not fair to blame the writer for that. Here is my try to explain the solution:

First, lets be clear about what we are looking for: The K largest sums of contiguous segments (fancy way of saying continuous segments) in the array. Note, that all the numbers in the array are positive.

So, if K is 1, we will simply choose the sum of all elements as the answer.

Now lets try K = 2. We will first choose the sum of all the numbers as the answer. But now comes the tricky part: which subsegment should we choose among the thousand available? Simply, the one with the largest sum. Note, (try an example by hand) that the choice for the largest one will be among the sum of elements at indices [0, N-2] or the sum of elements between indices [1, N-1]. (we can't choose [0, N-1] as that would be the sum of all elements, which we have already taken up).

With the last case, we have observed that choosing as large a range is good as all the numbers in the input are positive.

This leads us to the following theorem: If we are choosing the sum of segment [L, R] and if the segment [L-1, R] and/or the segment [L, R+1] is not yet taken up, then our choice of segment [L, R] is not optimal.

This leads us to the following algorithm:

let Best be a set of currently considered subsegments insert [0, N-1] into Best
for i = 1 -> K
Begin
let now = the highest summed segment
print the sum of now
let [L, R] be the start and end points of now
insert L+1, R and L, R-1 into Best
End

link

answered 17 Jun '16, 18:03

mjguru's gravatar image

4★mjguru
122
accept rate: 0%

edited 17 Jun '16, 18:07

My O(n^2) solution passed on this - https://www.codechef.com/viewsolution/9987811

Edit: It's actualy O(n^2 * log(n))

link

answered 01 May '16, 06:33

c1_6's gravatar image

6★c1_6
81110
accept rate: 0%

edited 01 May '16, 06:55

why did this gave runtime(sigsegv) all the the time?

include<stdio.h>

int main() { int n,i,j,s=0,t,a[1000],b[1000],k=1,m; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); i=1; j=1; while(i<=n) { while(j<=n) { s=s+a[j]; // printf("%d ",s); b[k]=s; k++; j++; } s=0; i++; j=i; } k=n*(n+1)/2; for(i=1;i<=k;i++) {

    for(j=1;j<=k;j++)
    {
        if(b[j]<=b[j+1])
        {
            t=b[j];
            b[j]=b[j+1];
            b[j+1]=t;
        }
    }
}
for(i=1;i<=m;i++)
printf("%d ",b[i]);
return 0;

}

link

answered 01 May '16, 14:03

abhi123_'s gravatar image

2★abhi123_
1
accept rate: 0%

why did this gave runtime(sigsegv) all the the time? plz help somebody?? https://www.codechef.com/viewsolution/9986008

link

answered 01 May '16, 14:07

abhi123_'s gravatar image

2★abhi123_
1
accept rate: 0%

for those who are getting runtime(sigsegv) , make sure your set S and vector array declaration in global space .

link

answered 01 May '16, 15:19

shuboy2014's gravatar image

2★shuboy2014
112
accept rate: 0%

@shuboy2014: By using S.rbegin() the array is sorted in descending order so as to access the first K elements from the front.

link

answered 01 May '16, 16:07

samarjeet27's gravatar image

4★samarjeet27
763
accept rate: 16%

confused to see the code

link

answered 01 May '16, 16:45

meight_888's gravatar image

0★meight_888
1
accept rate: 0%

somebody please explain the code , unable to understand some part of code.

link

answered 12 May '16, 20:18

geniusharshit's gravatar image

1★geniusharshit
1
accept rate: 0%

somebody please explain the code , unable to understand some part of code.

link

answered 12 May '16, 20:19

geniusharshit's gravatar image

1★geniusharshit
1
accept rate: 0%

not able to figure out why using priority_queue is giving wrong answer? http://ideone.com/YHTRJS

link

answered 22 May '16, 11:03

projjal16's gravatar image

2★projjal16
1
accept rate: 0%

is it named in any specific algorithm?

link

answered 15 Aug '18, 01:57

mehe's gravatar image

0★mehe
1
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,852
×1,409
×1,024
×850
×801
×57
×55

question asked: 19 Apr '16, 23:22

question was seen: 5,974 times

last updated: 15 Aug '18, 01:57