×

# KSUM - Editorial

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

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:

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}})$

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.

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".

1.7k11730
accept rate: 11%

19.8k350498541

 1 Complexity is O(K x log K) or O(K x log n) ?? Cause the size of the set is maximum n answered 01 May '16, 00:20 439●14 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★
 1 how did this pass? https://www.codechef.com/viewsolution/9987544 answered 01 May '16, 02:09 469●6●30 accept rate: 7%
 1 In editorial there is mistake , S.rbegin() instead of S.begin() . answered 01 May '16, 15:09 11●2 accept rate: 0%
 1 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 answered 17 Jun '16, 18:03 4★mjguru 12●2 accept rate: 0%
 0 My O(n^2) solution passed on this - https://www.codechef.com/viewsolution/9987811 Edit: It's actualy O(n^2 * log(n)) answered 01 May '16, 06:33 6★c1_6 81●1●10 accept rate: 0%

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;


}

2★abhi123_
1
accept rate: 0%

 0 why did this gave runtime(sigsegv) all the the time? plz help somebody?? https://www.codechef.com/viewsolution/9986008 answered 01 May '16, 14:07 2★abhi123_ 1 accept rate: 0%
 0 for those who are getting runtime(sigsegv) , make sure your set S and vector array declaration in global space . answered 01 May '16, 15:19 11●2 accept rate: 0%
 0 @shuboy2014: By using S.rbegin() the array is sorted in descending order so as to access the first K elements from the front. answered 01 May '16, 16:07 76●3 accept rate: 16%
 0 confused to see the code answered 01 May '16, 16:45 1 accept rate: 0%
 0 somebody please explain the code , unable to understand some part of code. answered 12 May '16, 20:18 1 accept rate: 0%
 0 somebody please explain the code , unable to understand some part of code. answered 12 May '16, 20:19 1 accept rate: 0%
 0 not able to figure out why using priority_queue is giving wrong answer? http://ideone.com/YHTRJS answered 22 May '16, 11:03 1 accept rate: 0%
 0 is it named in any specific algorithm? answered 15 Aug '18, 01:57 0★mehe 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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