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

1 Like

Complexity is

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

Cause the size of the set is maximum n

1 Like

how did this pass?

https://www.codechef.com/viewsolution/9987544

1 Like

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

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

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;

}

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

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

1 Like

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

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

confused to see the code

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.

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

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

not able to figure out why using priority_queue is giving wrong answer?

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

1 Like

is it named in any specific algorithm?