SPISPLTE - Editorial

editorial
, , ,
1

Practice
Contest

Author: vaibhav_0318
Tester: zombiedub
Editorialist: vaibhav_0318

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

prefix-sum, suffix-sum, sliding window

PROBLEM:

Given N machines generating chocolates given in a form of array A. Find the maximum amount of chocolates spider-man can get if he can take at most 3K chocolates by throwing 3 webs each of K size and get all the chocolates in the range selected. He cannot take a chocolate once taken. Spider-man cannot his throw on a machine more than once.

QUICK EXPLANATION:

Select a window of K size as a middle subarray and then select one left subarray of size K having maximum sum and then select one right subarray of size K and keep taking maximum of sum of three.

EXPLANATION:

Spider-man can choose one subarray of size K and throw his web at it. Now according to that middle subarray, he can choose the maximum sum subarray of size K in his left and his right. Thus making total choosen subarrays equal to 3 now, we can choose all such possible subarrays and keep taking maximum of them.

For this we follow these steps-

  • Create a prefix max array having maximum sum of all subarray ending before index i.
    We can do this by sliding window of size K from i = 0 to i=N-K and keep on taking maximum of all windows before and at i + K -1.

  • Create a suffix max array having maximum sum of all subarray starting from index i.By doing similar thing of sliding subarray of size K for all i = 0 to i=N-K and keep taking maximum of all the windows starting after and at i.

  • Select each possible middle subarray and keep on taking maximum of sum of middle subarray and maximum of sum of all previous subarray and maximum of sum of all forward subarray.

ans = max(ans, midSub[i] + preMax[i-1] + sufMax[i+k]) for all K \leq i \leq (n-k-1).

It is not possible to choose subarrays if 3K \ge N-1 . Because there must be atleast 3 disjoint subarrays of size K each.

PSEUDO CODE

   //max of sum of all elements of window size K ending before or at i  
   pre_max[i] = max(pre_max[i-1] ,sum of all elements from i-k+1 to i )
  //max of sum of all elements of window size K starting or at i 
   suf_max[i] = max(suf_max[i+1] ,sum of all elements from i to i+k-1)
  //traversing middle window of size k
   for all i from k to n-k-1
   ans = max(ans, suf of all elements from i to i+k-1)

SOLUTIONS

Solution 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(v,i) v.begin()+i,v.end()
#define en "\n"
#define mem(a,b) memset(a,b,sizeof(a));
#define F first
#define S second
#define mod 1000000007
#define mod2 998244353

typedef long long int ll;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int T=1,I;
    cin>>T;
    for(I=1;I<=T;I++){
    	ll n,k,i,s=0;
    	cin>>n>>k;
    	vector<ll> a(n),pre(n),suf(n);
    	for(i=0;i<n;i++){
    		cin>>a[i];
    	}
    	if(n-3*k<0){
    		cout<<-1<<en;
    		continue;
    	}
    	for(i=0;i<n;i++){
    		if(i<k){
    			s+=a[i];
    			if(i==k-1){
    				pre[i]=s;
    			}
    		}
    		else{
    			s-=a[i-k];
    			s+=a[i];
    			pre[i]=max(pre[i-1],s);
    		}
    	}
    	s=0;
    	for(i=n-1;i>=0;i--){
    		if(i>=n-k){
    			s+=a[i];
    			if(i==n-k){
    				suf[i]=s;
    			}
    		}
    		else{
    			s-=a[i+k];
    			s+=a[i];
    			suf[i]=max(suf[i+1],s);
    		}
    	}
    	s=0;
    	ll ans=0;
    	for(i=k;i<n-k;i++){
    		if(i<2*k){
    			s+=a[i];
    			if(i==2*k-1){
    				ans=max(ans,s+pre[i-k]+suf[i+1]);
    			}
    		}
    		else{
    			s-=a[i-k];
    			s+=a[i];
    			ans=max(ans,s+pre[i-k]+suf[i+1]);
    		}
    	}
    	cout<<ans;
        cout<<en;
    }
    return 0;
}

TIME COMPLEXITY

O(N)

1 Like