uet23_danh's blog

Maybe a DP problem?
By uet23_danh, history, 10 months ago, In English

Given an array $$$a$$$, you have to divide this array into maximum numbers of continous subarrays that the sum of a subarray is greater or equal to every subarrays that come after it. $$$1 \le n \le 5 \times 10^5, 1 \le a_i \le 10^9$$$.

Example:

Input

4
6 5 2 3

Output

3

A possible solutions:

6 | 5 | 2 3

Can anyone help me with this problems? I only came up with $$$O(n^2)$$$ solution. Thanks in advance!

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share problem link

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I don't have the submission link

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Link of this problem :IZHO 2019 day2 problem E.I solved this problem with binarysearch + dp.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you elaborate on that?

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        Let's assume (1<=i<=n) dp[i] — — maximum number of segment to position i. Let's assume (1 <= i <= n) val[i] — sum of segment that end in position i.Let's assume (1 <= i <= n) p[i] — is sum of elements to position i.Now let's calculate dp[i] we try to find maximum j such that (j + 1) to i is the last segment and (j < i) and (p[i]-p[j] >= val[j]) === (p[i] >= val[j] + p[j]). I tried my best I hope this is useful

        → Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

nvm

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a weird idea. Unsure if it works. Let's add all elements to a set each element is currently a subarray. If there's an element $$$x$$$ with an element $$$y$$$ after it such that $$$x < y$$$ then we remove $$$y$$$ from the set and add it to $$$x$$$. Can someone provide a case where this fails?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If I understood your idea correctly, $$$[3, 3, 4]$$$ would fail. Your idea would merge the last two elements making the array $$$[3, 7]$$$ which would need to be merged again. The optimal solution is to merge the first two elements making the array $$$[6, 4]$$$.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes that's what I meant. Thank you sir!

      → Reply