SPISPLT - Editorial

Practice
Contest

Author: vaibhav_0318
Tester: zombiedub
Editorialist: vaibhav_0318

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

prefix-sum, suffix-sum, sliding window, deque, sparse table, segment tree

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. But he is now given some magic power through which he can revive atmost L machines (L \leq K).

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. For choosing left and right subarray for each middle subarrays there are K-L+1 possibilities by giving a gap of K-L (by taking maximum of all subarrays before left one and maximum of all before right one) between end of pre_max subarray and start of suf_max subarray. We can take max of all these possibilities for each middle array but for selecting this maximum value we can optimise it using deque, sparse-table or segment-tree for getting final time complexity of O(N) or O(NlogN).

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.

Choosing left subarray and right subarray is the main key here. If we observe carefully then for all chosen middle subarrays we can consider all window of size K-L inside this middle subarray and take sum of pre_max of sum of all subarray of size K ending just before the start of this window and suf_max of sum of all subarray of size K starting just after the end of this subarray and keep taking max of sum of this chosen middle subarray, left subarray and right subarray.

We can pre compute pre_max and suf_max of sum of subarrays of size K by sliding window easily now for second objective we can precompute all subarrays by sliding window of size K-L and taking sum of pre_max ending just before the start of this window and suf_max staring just after the end of this window. Let’s call it sub2.

sub2[i] = preMax[i] + sufMax[i+k-l] such that i+K-L \leq N-K.

Now, when calculating final answer while traversing middle subarray we can take max of all such possible window inside this subarray in O(1) time using deque. By doing pre computation of O(NlogN) it can be done using segment-tree in O(logN) and in O(1) using sparse table.

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.

  • Create sub2 array such that sub2[i] = preMax[i] + sufMax[i+k-l] such that i+K-L \leq N-K.

  • Select each possible middle subarray and take 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. We can do this by deque using this way of selecting max of subarrays in a range. We can do same using sparse table using this way or segment tree using this way.

We cannot choose such subarray under given conditions if 3K-L \geq N-1. Since we need at least this size of subarray.

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);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
        int T=1,I;
        cin>>T;
        for(I=1;I<=T;I++){
        	ll n,k,l,i,s=0;
        	cin>>n>>k>>l;
        	vector<ll> a(n),sub(n),p_mx(n),s_mx(n);
        	for(i=0;i<n;i++){
        		cin>>a[i];
        	}
        	if(3*k-l>n){
        		cout<<-1<<en;
        		continue;
        	}
            // pre computing all possible subarrays and creating pre_max(p_mx) of them.
        	for(i=0;i<n;i++){
        		if(i<k){
        			s+=a[i];
        			if(i==k-1){
        				sub[i-k+1]=s;
        				p_mx[i]=s;
        				
        			}
        		}
        		else{
        			s-=a[i-k];
        			s+=a[i];
        			sub[i-k+1]=s;
        			p_mx[i]=max(sub[i-k+1],p_mx[i-1]);
        		}
        	}
     		// pre computing suf_max(p_mx) of all possible subarrays.
        	s_mx[n-k]=sub[n-k];
        	for(i=n-k-1;i>=0;i--){
        		s_mx[i]=max(sub[i],s_mx[i+1]);
        	}
            // computing sub2
        	vector<ll> sub2(n);
        	ll d=k-l;
        	for(i=k-1;i+k+d+1<=n;i++){
        		sub2[i]=p_mx[i]+s_mx[i+d+1];
        	}

            // traversing middle subarray and checking all possible answers.
        	ll ans=INT_MIN;
        	deque<ll> dq;
        	for(i=k-l;i<=n-(k-l)-k;i++){
        		while(i+k+d+1<=n && !dq.empty() && sub2[dq.back()]<sub2[i+l-1]){
        			dq.pop_back();
        		}
        		if(i+k+d+1<=n)
        			dq.push_back(i+l-1);
        		if(dq.front()+1<i)dq.pop_front();	
        		ll mx=dq.front();
        		ans=max(ans,sub[i]+sub2[mx]);
        	}
        	cout<<ans;

            cout<<en;
        }
        return 0;
    }

TIME COMPLEXITY

O(N) or O(NLogN) depending on data structure used for finding max of subarray.