Kr_Shubham's blog

Help- Counting Ways to Partition an Array into Segments with Positive Sum
By Kr_Shubham, history, 2 months ago, In English

Find the number of ways to partition array into segments such that sum of each segments is greater than 0,

Note- Concatenating the segments should result into full array.

Constraints: 1<=N<=10^5 1<=a[I]<=10^9 Example:

Input1: N=3, a[]={-1,-3,7}

Output: 1. (Complete array as one Segment)

Thanks

PS. This is not part of any running Contest.

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

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

Auto comment: topic has been updated by Kr_Shubham (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Let $$$[p_0, p_1, p_2,\dots, p_n]$$$ be the prefix sum array of $$$a$$$. More formally, $$$p_0 = 0$$$ and $$$p_i = \displaystyle\sum_{j=1}^i a_j$$$ for $$$1 \le i \le n$$$.

Every partition of the original array into subarrays can be represented by a unique subsequence of prefix sums that always contains $$$p_0$$$ an $$$p_n$$$:

Let $$$a = [1, -2, 3, -4, 5]$$$. Thus, $$$p = [0, 1, -1, 2, -2, 3]$$$.

Let's partition $$$a$$$ like this: $$$[1], [-2, 3], [-4, 5]$$$. We will now choose the subsequence of $$$p$$$ containing $$$p_0$$$ and all prefix sums at the end of any chosen subarray, i.e. our subsequence will be $$$[p_0, p_1, p_3, p_5] = [0, 1, 2, 3]$$$.

Notice that the sum in any subarray in our partition is the difference of two consecutive prefix sums in this subsequence. Since every subarray must have a positive sum, this subsequence must be strictly increasing.

Thus, we can rephrase the problem as follows: Given an array $$$a$$$, count the number of increasing subsequences of the prefix sum array of $$$a$$$ that contain the first and last elements $$$p_0$$$ and $$$p_n$$$. Counting the number of increasing subsequences is a standard problem that can be solved in $$$O(n\log n)$$$ time with coordinate compression and fenwick/segment trees.

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

    Thanks,Nice explanation

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

    Hey, what if you wanna count it without seg/fenwick? is there any way?

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

      I don't know of any subquadratic aolution without fenwick/segtree and I don't think an easier solution exists.

      → Reply