Recently, I have participated in school contest and I got this problem:

The problem is to generalize a formula for the probability P in terms of weights $$$w$$$ and sums $$$S$$$ for a given $$$n$$$, where $$$S=\sum_{j=1}^{n} w_j$$$

The probability formula involves choosing a permutation of the set $$$[2, n]$$$, which means the number of terms grows rapidly with $$$n$$$. Let's try to understand the general pattern by analyzing the cases for $$$n=3$$$ and $$$n=4$$$

$$$\textbf Case \ n = 3$$$

Given: $$$S = w_1 + w_2 + w_3$$$

For $$$n=3$$$, the formula for $$$P$$$ is:

We can factor the expression:

This represents the weighted sum of two terms where the denominators correspond to the differences between $$$S$$$ and individual terms $$$w_2$$$ and $$$w_3$$$

$$$\textbf Case \ n = 4$$$

Now, let's analyze the case for $$$n=4$$$, where the formula involves more permutations:

The expanded form looks like:

Group similar terms by factoring:

$$$\textbf Generalizing\ to\ n$$$

For any $$$n$$$, the general form of the probability formula is:

The pattern is that for each permutation of $$${2, 3, ..., n}$$$ , the numerator is the product of all $$$w_i$$$'s and the denominator involves nested sums subtracting successive terms of the permutation from $$$S$$$

$$$\textbf Recursive\ Structure$$$

The denominator has a recursive structure:

However, I don't really know how to compute $$$P$$$ with the given constraints like this

$$$1 \leq n \leq 5000$$$

$$$w_i > 0$$$ and $$$1 \leq \sum^{n}_{i=1} w_i <= 10^5$$$

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

#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!