BCLGSUBH - Editorial

PROBLEM LINK:

Practice

Author: vaibhav_0318
Tester: zombiedub
Editorialist: vaibhav_0318

DIFFICULTY:

Hard

PREREQUISITES:

Dynamic Programming

PROBLEM:

Choose K disjoint distinct subarrays each of length L from an array of size N such that their sum is maximum. Also, you are allowed to choose at most C elements twice in a subarray.

EXPLANATION:

Let’s choose K subarrays one by one. For choosing xth subarray suppose we already have best possible answer for 0 common element, 1 common element …C common elements for each array from [0, i] for x-1 subarrays. Now if we want to choose xth subarray from [i+1,i+L] then:

For 0 common elements with subarray [i+1, i+L] best possible ans is: max( ans for x-1th subarray till i such that C elements are common, ans for x-1th subarray till i such that C-1 elements are common…, ans for x-1th subarray till i such that 0 elements are common) + sum of subarray [i+1, i+L].

Similarly, for 1 common elements with subarray [i+1,i+L] best possible ans is: max( ans for x-1th subarray till i+1 such that C-1 elements are common, ans for x-1th subarray till i+1 such that C-2 elements are common…, ans for (x-1)th subarray till i+1 such that 0 elements are common) + sum of subarray [i+1, i+L].

Similarly, we can choose best answer with subarray [i+1,i+L] for 2 commons,3 commons…C commons.

Now, in the same way, we can find best solution for K subarrays.

For formally,
Dp[Nth][last\_index\_of\_subarray][Cth\_common] = max(Dp[(N-1)th][last\_index\_of\_subarray -L+ Cth\_common][C- Cth\_common] + sum\_of\_subarray[last\_index\_of\_subarray - L+1,last\_index\_of\_subarray], X)

where,

  • Dp[i][j][k] denotes best answer for choosing ith subarray(0 \leq i \leq K) till jth index and for k commons.
  • sum\_of\_subarray[i,j] is the sum of subarray in range [i,j] (0 \leq i \leq j \leq N-1)
  • X = max(Dp[Nth][last\_index\_of\_subarray-1][Cth\_common], Dp[Nth][last\_index\_of\_subarray][Cth\_common-1])

TIME COMPLEXITY:

O(N*K*C)

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, j, o, c;
        cin >> n >> k >> l >> c;
        ll a[n + 1], pre[n + 1];
        pre[0] = 0;
        for (i = 1; i <= n; i++) {
            cin >> a[i];
            pre[i] = pre[i - 1] + a[i];
        }
        if ((k * l - ((k / 2)*c)) > n) {
            cout << -1 << en;
            continue;
        }
        vector<vector<ll>> dp(n + 1, vector<ll> (c + 1));
        ll ans = 0;

        for (i = 1; i <= k; i++) {
            vector<vector<ll>> dp1(n + 1, vector<ll> (c + 1));

            for (j = l; j <= n; j++) {
                for (o = 0; o <= c; o++) {
                    dp1[j][o] = max(dp[j - l + o][c - o] + pre[j] - pre[j - l], dp1[j - 1][o]);
                    if (o > 0)
                        dp1[j][o] = max(dp1[j][o], dp1[j][o - 1]);
                }
            }
            dp = dp1;
        }
        for (i = 1; i <= n; i++)for (j = 0; j <= c; j++)ans = max(ans, dp[i][j]);

        cout << ans << en;
    }
    return 0;
}

Can someone tell me the new subarrays formed for this test case.
1
6 3 4 3
1 2 3 4 5 6.
Answer for this test case comes out to be 42, according to editorial’s solution.