HockeySticks | Topcoder Archive

Problem Statement

Given an array A, an inversion is a pair of indices (i, j) such that i < j but A[i] > A[j].

A triple inversion is then a triple of indices (i, j, k) such that all three pairs (i, j), (j, k) and (i, k) are inversions.

For example, in the array A = {10, 20, 30, 80, 50, 60, 40, 70} the pair of indices (4, 6) is an inversion because 4 < 6 while A[4] = 50 > A[6] = 40. The pairs (3, 4) and (3, 6) are also inversions, which makes (3, 4, 6) a triple inversion.

A hockey stick is a 4-tuple of indices (i, j, k, l) such that (i, j, k) is a triple inversion, k < l, and (k, l) is not an inversion.

In the array A from the previous example the 4-tuple of indices (3, 4, 6, 7) is an example of a hockey stick.

You are given an array A. (The exact input format is specified below.) Count all hockey sticks in A and return their count modulo (10^9 + 7).

In order to keep the input size small while still allowing meaningful challenges, most of the array A will be pseudorandom. You are given its length N, a modulus M, and the int[] Aprefix with a prefix of the array A. Please use the pseudocode below to generate the rest of A. Watch out for integer overflow: use 64-bit integers during the calculation where appropriate.


L = length(Aprefix)

allocate an array A[0..N-1]

for i = 0 to L-1:
    A[i] = Aprefix[i]

for i = L to N-1:
    A[i] = (A[i-1] * 1103515245 + 12345) modulo 2^31

for i = L to N-1:
    A[i] = A[i] modulo M

Definition

Class:: HockeySticks
Method:: count
Parameters:: int, int, int[]
Returns:: int
Method signature:: int count(int N, int M, int[] Aprefix)
(be sure your method is public)

Notes

The reference solution does not depend on the input being pseudorandom, it would correctly solve any input of the size allowed by Constraints.

Constraints

N will be between 4 and 100,000, inclusive.
M will be between 1 and 10^9, inclusive.
Aprefix will have between 1 and N elements, inclusive.
Aprefix will have at most 100 elements.
Each element of Aprefix will be between 0 and M-1, inclusive.

Examples

```
8
```
```
1000000
```
```
{10, 20, 30, 80, 50, 60, 40, 70}
```
```
Returns: 2
```
The example from the problem statement. The two hockey sticks are (3, 4, 6, 7) and (3, 5, 6, 7).

{47, 47, 47, 47, 47, 47, 47, 47}

Returns: 0

No hockey sticks anywhere.

```
8
```
```
1000000
```
```
{49, 48, 47, 47, 47, 47, 47, 47}
```
```
Returns: 15
```
Each 4-tuple (0, 1, x, y) with 1 < x < y is a hockey stick.
```
20
```
```
100
```
```
{49, 48, 47}
```
```
Returns: 772
```
The generated array A should be {49, 48, 47, 8, 5, 98, 91, 48, 33, 50, 27, 76, 37, 66, 23, 0, 81, 2, 75, 72}. The temporary values in A produced during the generation of A (before applying "modulo M" to all of them): {49, 48, 47, 325621308, 263614405, 1041878298, 160854091, 1346820648, 663962433, 1031250150, 1993983527, 507736276, 118477437, 1569514866, 722640323, 181454400, 1288444281, 1329587902, 1802982175, 1176241772}.

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.