PROBLEM LINK:Author: 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<=K1; 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. Subtask 2It 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...N1$. Let us assume that the second largest is obtained from the range $1...N1$. Then, the third largest sum will be maximum of sum of range $2...N$ ( previous range left ), range $2...N1$ and range $1...N2$ ( 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 R1]$ 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[i1] + 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({sumarr[L], {L+1, R}}); S.insert({sumarr[R], {L, R1}}); } } } TIME COMPLEXITY:$O(K \times \log{K})$ AUTHOR'S AND TESTER'S SOLUTION:Author's solution can be found here.
This question is marked "community wiki".
asked 19 Apr '16, 23:22

how did this pass? answered 01 May '16, 02:09

In editorial there is mistake , S.rbegin() instead of S.begin() . answered 01 May '16, 15:09

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, N2] or the sum of elements between indices [1, N1]. (we can't choose [0, N1] 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 [L1, 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, N1] into Best answered 17 Jun '16, 18:03

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

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++) {
} answered 01 May '16, 14:03

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

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

@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

somebody please explain the code , unable to understand some part of code. answered 12 May '16, 20:18

somebody please explain the code , unable to understand some part of code. answered 12 May '16, 20:19

not able to figure out why using priority_queue is giving wrong answer? http://ideone.com/YHTRJS answered 22 May '16, 11:03
