Dividing an array into K subarrays to reduce the largest possible difference.

#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
2	atcoder_official	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

First of all, Sorry for my poor English.

I know there's a blog which discusses about this problem before: https://codeforces.net/blog/entry/52860. However I am not really understand the solution for it.

Well, here's the problem statement: You are given an array $$$a$$$ with $$$n$$$ elements. Your task is to divide the array $$$a$$$ into $$$k$$$ subarrays so that the difference between the largest and the smallest value of all subarrays is minimum (The value of a subarray is the sum of all elements in that subarray). Constraints: $$$ 1 \leq K \leq N \leq 250,\ 0 \leq a[i] \leq 10^6\ \forall i \in [1, n] $$$

So let's take an example: $$$N=6$$$ and $$$K=3$$$ and the array $$$a = {7, 4, 6, 1, 2, 10}$$$

The optimal way is to split it into $$$[7, 4][6, 1, 2][10] \rightarrow$$$ The value of each subarray is $$$11\ (= 7 + 4), 9\ (= 6 + 1 + 2), 10\ (= 10)$$$. Here the largest value is $$$11$$$ and the smallest one is $$$9$$$ so the answer is $$$11 - 9 = 2$$$

Actually I did attempt to code this problem. If you want to see, I put it below

Code

#include <bits/stdc++.h>

using namespace std;
#define maxN 255
typedef long long ll;
const ll INF = 1e18;
ll N, K, a[maxN], pref[maxN];
struct State {
    ll max_sum, min_sum, range;
    State() : max_sum(-INF), min_sum(INF), range(INF) {}
};
State dp[maxN][maxN];

void Solve() {
    pref[0] = 0;
    for (ll i = 1; i <= N; ++i)
        pref[i] = pref[i-1] + a[i-1];

    for (ll i = 0; i <= N; ++i)
        for (ll j = 0; j <= K; ++j)
            dp[i][j] = State();

    for (ll k = 1; k <= K; ++k) {
        for (ll i = k; i <= N; ++i) {
            for (ll j = k - 1; j < i; ++j) {
                ll segment_sum = pref[i] - pref[j];
                ll new_max_sum = max(segment_sum, dp[j][k-1].max_sum);
                ll new_min_sum = min(segment_sum, dp[j][k-1].min_sum);
                ll new_range = new_max_sum - new_min_sum;
                if (new_range < dp[i][k].range) {
                    dp[i][k].max_sum = new_max_sum;
                    dp[i][k].min_sum = new_min_sum;
                    dp[i][k].range = new_range;
                }
            }
        }
    }
    cout<<dp[N][K].range<<"\n";
}

void ReadData() {
    ll T; cin>>T; while (T--) {
        cin>>N>>K;
        for (ll i = 0; i < N; ++i)
            cin>>a[i];
        Solve();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ReadData(); return 0;
}

My algorithm is to use Dynamic Programming where $$$dp[i][j]$$$ denotes the answer for the segment from $$$1$$$ to $$$i$$$ which is being divided into $$$j$$$ subarrays. So the final answer would be $$$dp[N][K]$$$ and time complexity would be $$$O(N^2 \times K)$$$. However, I don't know if this is the exact solution which solves all the cases for this problem. Therefore, I want you guys to point me out is there any errors in my code as well as give me some hints if they are wrong. Thanks a lot!

Comments (12)

Write comment?

Icelast

3 months ago, # |

10 5 172175 314751 42278 124175 323274 156404 723022 324395 809542 290212

→ Reply

nguyenkhangninh99

5 weeks ago, # ^ |

dep trai!

dorijanlendvaj

+13

I have a solution that works in $$$O(\frac{n^3k \log{n}}{64})$$$ time, 0.6 seconds on a max test locally. The idea is to make a sorted array of all subarray sums and to use 2 pointers to see, for each sum that we choose to make the maximum, what's the highest minimum sum we can make. To figure out if it's possible to split the array into $$$k$$$ subarrays given a minimum and maximum sum, let $$$dp[i][j]$$$ be 1 if the first $$$i$$$ elements can be split into $$$j$$$ subarrays with the given minimum and maximum sum, and 0 otherwise. For transitions, we can use 2 pointers to see for each right end of the subarray what range of the left ends of the subarray has the sum between the minimum and maximum allowed sum, and $$$dp[i][j]$$$ is true if $$$dp[x][j-1]$$$ is true for any $$$x$$$ inside that range. This can be handled with a segment tree and bitsets; if we consider each $$$dp[i]$$$ as a bitset of size $$$k$$$, then $$$dp[i]$$$ is simply the bitwise OR of all $$$dp[x]$$$ in the range shifted by 1. Code:

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=255,M=1<<8;
const char en='\n';
const ll LLINF=1ll<<60;

bitset<N> seg[M*2+10],praz;

void upd(int i,bitset<N> x)
{
	for (i+=M;i;i/=2) seg[i]|=x;
}

bitset<N> ge(int l,int r)
{
	bitset<N> odg=praz;
	for (l+=M,r+=M;l<r;l/=2,r/=2)
	{
		if (l&1) odg|=seg[l++];
		if (r&1) odg|=seg[--r];
	}
	return odg;
}

int t,n,k,h[N],pr[N];

bool pos(int mins,int maxs)
{
	for (int i=0;i<2*M;++i) seg[i]=praz;
	auto r0=praz;
	r0[0]=1;
	upd(0,r0);
	int firstleqmaxs=0,firstlessmins=0;
	for (int r=1;r<=n;++r)
	{
		while (pr[r]-pr[firstleqmaxs]>maxs) ++firstleqmaxs;
		while (pr[r]-pr[firstlessmins]>=mins) ++firstlessmins;
		upd(r,ge(firstleqmaxs,firstlessmins)<<1);
	}
	return seg[n+M][k];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>k;
		for (int i=0;i<n;++i) cin>>h[i],pr[i+1]=pr[i]+h[i];
		vi sums;
		for (int i=0;i<n;++i) for (int j=i+1;j<=n;++j) sums.pb(pr[j]-pr[i]);
		sort(all(sums));
		int l=-1,mi=1e9;
		for (int r=0;r<(int)sums.size();++r)
		{
			while (l<(int)sums.size()-1 && pos(sums[l+1],sums[r])) ++l;
			if (l>=0) mi=min(mi,sums[r]-sums[l]);
		}
		cout<<mi<<en;
	}
}