LexicographicPartition | Topcoder Archive

Problem Statement

An array A is called positive partitionable if we can divide A into one or more contiguous subarrays such that each element belongs to exactly one of the subarrays and the sum of each subarray is positive.

For example, the array {3,-7,8} is positive partitionable. One valid way of splitting this array is to split it into {3} and {-7,8}. The array {0,1,0,1,2} is also positive partitionable. The array {-1,2,-3,4,-5} and the array {0} are not positively partitionable.

A partition of an array can be described by listing the lengths of the partitions, in order. For example, {3} has length 1 and {-7,8} has length 2, hence the partition of {3,-7,8} into {3} and {-7,8} can be described by the sequence {1,2}. The sequences {2,3}, {2,2,1}, and {4,1} describe different three valid ways of partitioning the sequence {0,1,0,1,2}.

You are given the int n, the int[] Aprefix, and the ints seed and Arange. Use the following pseudocode to generate an array A with n elements:

for i = 0 .. len(Aprefix)-1:
    A[i] = Aprefix[i]

state = seed
for i = len(Aprefix) .. n-1:
    state = (1103515245 * state + 12345)
    A[i] = state modulo (2*Arange+1)
    A[i] = A[i] - Arange
    state = state modulo 2^31

If this array A isn't positive partitionable, return {-1}. Otherwise, find an array B that describes a valid partition of A. If there are multiple possibilities for B, pick the lexicographically smallest one. Return an array that contains the value length(B) and then the first min(len(B),200) elements of B, in order.

Definition

Class:: LexicographicPartition
Method:: positiveSum
Parameters:: int, int[], int, int
Returns:: int[]
Method signature:: int[] positiveSum(int n, int[] Aprefix, int seed, int Arange)
(be sure your method is public)

Notes

Given two different sequences A[0..a-1] and B[0..b-1] such that neither is a prefix of the other, the lexicographically smaller sequence is the one that has a smaller value at the first index at which they differ. For example, {3, 7, 100} < {3, 10, 12, 45} because 7 < 10.

Constraints

n will be between 1 and 200,000 inclusive.
All elements of Aprefix will be between -10^6 and 10^6 inclusive.
Aprefix will contain between 0 and min(n,500) elements inclusive.
seed will be between 1 and 10^9 inclusive.
Arange will be between 0 and 10^6 inclusive.

Examples

```
3
```
```
{3,-7,8}
```
```
1
```
```
1
```
```
Returns: {2, 1, 2 }
```
A = {3,-7,8}. The lexicographically smallest sequence that describes a valid partition is indeed the sequence B={1,2} mentioned in the statement. Thus, we return the array {length(B),1,2} = {2,1,2}.
```
5
```
```
{0,1,0,1,2}
```
```
42
```
```
47
```
```
Returns: {3, 2, 2, 1 }
```
The optimal B is {2,2,1}.
```
5
```
```
{-1,2,-3,4,-5}
```
```
777
```
```
4747
```
```
Returns: {-1 }
```
```
1
```
```
{0}
```
```
12
```
```
34
```
```
Returns: {-1 }
```

{4,-7,4,-7}

123456789

Returns: {6, 1, 5, 1, 1, 1, 1 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.