Array Break
The D.E. Shaw Group● HardOAProblem statement
There is an integer array arr of length n. Two arrays b and c are called a perfect break of arr if:
- The lengths of arrays
bandcaren. - Elements in array
bare in non-decreasing order. - Elements in array
care in non-increasing order. - They satisfy
b[i] ≥ 0,c[i] ≥ 0, andb[i] + c[i] = arr[i], for eachiwhere0 ≤ i < n.
Find the number of possible perfect breaks of arr. Since the number can be large, return the value modulo 1000000007, i.e., (10^9+7).
Function
perfectBreak(arr: int[]) → int
Complete the function perfectBreak in the editor.
perfectBreak has the following parameter:
int arr[n]: the num of possible perfect breaks modulo (109 + 7).
Examples
Example 1
arr = [2, 3, 2]return = 4
There are 4 possible perfect breaks of array arr:
b = [0, 1, 1],c = [2, 2, 1]is a perfect break because it
- b and c have 3 elements
- b is non-decreasing order
- c is in non-increasing order
- elements of b and c are 0 or more than the sums of a[i] + b[i] = [2, 3, 2], which matches arr.
b = [0, 1, 2],c = [2, 2, 0]is a perfect break.b = [0, 2, 2],c = [2, 1, 0]is a perfect break.b = [1, 2, 2],c = [1, 1, 0]is a perfect break.b = [1, 3, 2],c = [1, 0, 0]is not a perfect break becausebis not non-decreasing.b = [1, 2, 2],c = [2, 1, 0]is not a perfect break becauseb[0] + c[0] ≠ arr[0].
Example 2
arr = [3, 2]return = 6The perfect breaks are: b = [0, 0], c = [3, 2] b = [0, 1], c = [3, 1] b = [0, 2], c = [3, 0] b = [1, 1], c = [2, 1] b = [1, 2], c = [2, 0] b = [2, 2], c = [1, 0]
Constraints
1 <= n <= 30001 <= arr[i] <= 3000