Блог пользователя BinhPhamT

Автор BinhPhamT, история, 4 недели назад, По-английски

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:

$$$\Large P = \frac{w_2 \cdot w_3}{S \cdot (S - w_2)} + \frac{w_2 \cdot w_3}{S \cdot (S - w_3)}$$$

We can factor the expression:

$$$\Large P = \frac{w_2 \cdot w_3}{S} \left( \frac{1}{S - w_2} + \frac{1}{S - w_3} \right)$$$

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:

$$$\Large P = \sum_{\text{all permutations of } {2, 3, 4}} \frac{w_2 \cdot w_3 \cdot w_4}{S \cdot (S - w_2) \cdot (S - w_2 - w_3)}$$$

The expanded form looks like:

$$$\Large P = \frac{w_2 \cdot w_3 \cdot w_4}{S \cdot (S - w_2) \cdot (S - w_2 - w_3)} + \cdots \quad \text{(5 more similar terms)}$$$

Group similar terms by factoring:

$$$\Large P = \frac{w_2 \cdot w_3 \cdot w_4}{S} \left( \frac{1}{(S - w_2)(S - w_2 - w_3)} + \frac{1}{(S - w_2)(S - w_2 - w_4)} + \cdots \right)$$$

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

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

$$$P = \sum_{\text{all permutations of } {2, 3, \dots, n}} \frac{\prod_{i=2}^{n} w_i}{S \cdot (S - w_{i_2}) \cdot (S - w_{i_2} - w_{i_3}) \cdot \cdots \cdot (S - w_{i_2} - w_{i_3} - \cdots - w_{i_{n-1}})}$$$

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:

$$$ P = \frac{\prod_{i=2}^{n} w_i}{S} \sum_{\text{permutations}} \prod_{j=2}^{n-1} \frac{1}{S - w_{i_2} - w_{i_3} - \cdots - w_{i_j}} $$$

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$$$

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор BinhPhamT, история, 7 недель назад, По-английски

First of all, Sorry for my poor English.

I know there's a blog which discusses about this problem before: https://codeforces.me/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

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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится