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

Автор Kr_Shubham, история, 3 месяца назад, По-английски

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.

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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.