Question about an array's problem

Правка en4, от tantam75, 2017-12-20 14:40:17

(Sorry for my bad english!!)

Problem (QBSEGPAR — Vietnam Olympiad of Informatics 2005): For an integer array a1, a2, ..., an and a integer k. Determine the smallest integer M to divide the array into k non-empty paths so that the sum of the elements in each paths does not exceed M.

  • Constraints: k ≤ n ≤ 15000, |ai| ≤ 30000.

UPD: 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 paths: [4, 3], [2], [1, 5]. You can also represent one way to divide the array into k paths by an array x1, x2, ..., xk (1 ≤ x1 < x2 < ... < xk = n) which path ith (i > 2) is subarray [xi - 1 + 1..xi] (first path is subarray [1..x1]).

I have an 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 paths so that the sum of the elements in each of j paths does not exceed M. Otherwise, f(i, j) = false. Then we can divide array a[1..n] into k satisfied path 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:

  • fi = minimum number of paths which has sum of elements does not exceed M that you could divide from array a[1..i].
  • gi = maximum number of paths which has sum of elements does not exceed M that you could divide from array a[1..i].

Required complexity is o(nlogn2). We can calculate f and g by o(nlogn) dp, which need segment tree or Fenwick tree (i haven't done it), or simple o(n2) dp. Okay, now here is the checking path, which is unclear to me: The solution said that array a[1..n] could divide into k satisfied paths if fn ≤ k ≤ gn. I think this might not be right. In my opinion, we can divide array a[1..n] into minimum fn satisfied paths, maximum gn satisfied paths, but it doesn't mean we can divide the array into k satisfied paths which fn ≤ k ≤ gn.

Could you tell me how to prove this solution right or wrong? Thanks for your help!

Теги binary seach, dp, segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский tantam75 2017-12-20 15:03:35 33
en5 Английский tantam75 2017-12-20 14:43:07 2 Tiny change: 'th$ $(i > 2)$ is suba' -> 'th$ $(i > 1)$ is suba'
en4 Английский tantam75 2017-12-20 14:40:17 405 Tiny change: ' to divide: $[4,3], ' -> ' to divide the array into 3 paths: $[4,3], '
en3 Английский tantam75 2017-12-20 06:11:05 4
en2 Английский tantam75 2017-12-20 06:09:05 6
en1 Английский tantam75 2017-12-20 06:07:28 1849 Initial revision (published)