(Sorry for my bad english!!)↵
↵
Problem (QBSEGPAR — Vietnam Olympiad of Informatics 2005): For an integer array $a_1, a_2, ..., a_n$ and a integer $k$. Determine the smallest integer $M$ to divide the array into $k$ non-empty pathrts so that the sum of the elements in each pathrts does not exceed $M$.↵
↵
- Constraints: $k \leq n \leq 15000, |a_i| \leq 30000$.↵
↵
<strong>UPD:</strong> For example, we have $n = 5, k = 3$, and the array is $4, 3, 2, 1, 5$. Then here is one way to divide the array into 3 pathrts: $[4,3], [2], [1,5]$. You can also represent one way to divide the array into k pathrts by an array $x_1, x_2, ..., x_k$ $(1 \leq x_1 < x_2 < ... < x_k = n)$ which pathrt $i^th$ $(i > 1)$ is subarray $[x_{i-1}+1$..$x_i]$ (first pathrt is subarray $[1..x_1]$). ↵
↵
I have an $o(n^3 \relax log n)$ solution, which we do binary seaching for $M$, and dp to check if this $M$ could satisfy (let $f(i,j) = true$ means you could divide array $a[1..i]$ into $j$ pathrts so that the sum of the elements in each of $j$ pathrts does not exceed $M$. Otherwise, $f(i,j) = false$. Then we can divide array $a[1..n]$ into $k$ satisfied pathrts if $f(n,k) = true$). Of course this couldn't pass all tests.↵
↵
Then I checked for the solution. Here is it, we also do binary searching for $M$, but for each $M$, we do a different dp:↵
↵
- $f_i$ = minimum number of pathrts which has sum of elements does not exceed $M$ that you could divide from array $a[1..i]$.↵
- $g_i$ = maximum number of pathrts which has sum of elements does not exceed $M$ that you could divide from array $a[1..i]$.↵
↵
Required complexity is $o(n logn^2)$. We can calculate $f$ and $g$ by $o(n logn)$ dp, which need segment tree or Fenwick tree (i haven't done it), or simple $o(n^2)$ dp. Okay, now here is the checking pathrt, which is unclear to me: The solution said that array $a[1..n]$ could divide into $k$ satisfied pathrts if $f_n \leq k \leq g_n$. I think this might not be right. In my opinion, we can divide array $a[1..n]$ into minimum $f_n$ satisfied pathrts, maximum $g_n$ satisfied pathrts, but it doesn't mean we can divide the array into $k$ satisfied pathrts which $f_n \leq k \leq g_n$.↵
↵
Could you tell me how to prove this solution right or wrong? Thanks for your help!
↵
Problem (QBSEGPAR — Vietnam Olympiad of Informatics 2005): For an integer array $a_1, a_2, ..., a_n$ and a integer $k$. Determine the smallest integer $M$ to divide the array into $k$ non-empty pa
↵
- Constraints: $k \leq n \leq 15000, |a_i| \leq 30000$.↵
↵
<strong>UPD:</strong> For example, we have $n = 5, k = 3$, and the array is $4, 3, 2, 1, 5$. Then here is one way to divide the array into 3 pa
↵
I have an $o(n^3 \relax log n)$ solution, which we do binary seaching for $M$, and dp to check if this $M$ could satisfy (let $f(i,j) = true$ means you could divide array $a[1..i]$ into $j$ pa
↵
Then I checked for the solution. Here is it, we also do binary searching for $M$, but for each $M$, we do a different dp:↵
↵
- $f_i$ = minimum number of pa
- $g_i$ = maximum number of pa
↵
Required complexity is $o(n logn^2)$. We can calculate $f$ and $g$ by $o(n logn)$ dp, which need segment tree or Fenwick tree (i haven't done it), or simple $o(n^2)$ dp. Okay, now here is the checking pa
↵
Could you tell me how to prove this solution right or wrong? Thanks for your help!
