WeirdTriangle | Topcoder Archive

Problem Statement

You are given an array L containing N integers. Count the number of ways in which we can choose three indices (i,j,k) such that 0 <= i < j < k <= N-1 and it is possible to constuct a non-degenerate triangle whose side lengths are L[i]+L[j], L[j]+L[k], and L[k]+L[i].

In a non-degenerate triangle, all sides have positive lengths and the triangle has a positive area.

You are given N, the int[] B containing a prefix of L, and ints seed and MX. Use the following pseudocode to generate the array L:

A[0] = seed
for i=1 to N-1:
	A[i] = (A[i-1]*1103515245 + 12345) modulo 2147483648

for i=0 to len(B)-1:
        L[i] = B[i]

for i=len(B) to N-1:
	L[i] = 2*(A[i] modulo MX) - MX + 1

Definition

Class:: WeirdTriangle
Method:: findAllTriangle
Parameters:: int, int[], int, int
Returns:: long
Method signature:: long findAllTriangle(int N, int[] B, int seed, int MX)
(be sure your method is public)

Notes

The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

N will be between 1 and 10,000,000,000,000,000, inclusive.
P will be between 1 and 10,000,000,000,000,000, inclusive.
K will be between 1 and 1,000, inclusive.
Q will be between 1 and 1,000, inclusive.

Examples

```
3
```
```
{-2, -3, -5}
```
```
0
```
```
10
```
```
Returns: 0
```
L = B = {-2, -3, -5}. The only triple of indices is (0,1,2), but the corresponding side lengths are -5, -8, and -7. A non-degenerate triangle must have positive side lengths, so there are no valid triples of indices and the answer is zero.
```
4
```
```
{1, 4, 6}
```
```
200
```
```
100
```
```
Returns: 1
```
Here, L = {1, 4, 6, -45}. The triple (i,j,k) = (0,1,2) gives us edge lengths 5, 10, and 7. These are indeed side lengths of a non-degenerate triangle. For any other triple of indices two of the side lengths will be negative, so there are no other valid triples.
```
2
```
```
{5,6}
```
```
0
```
```
10
```
```
Returns: 0
```
Since N=2, there are no triples of indices, hence the answer is zero.

{}

777818934

1000000000

Returns: 133390319026380

Note that B may be empty.

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.