Connection Status:
Competition Arena > WeirdTriangle

WeirdTriangle

SRM 763 · 2019-07-16 · by vivek1998299

SRM 763 · 2019-07-16 · by vivek1998299 · Simple Math
Class Name: WeirdTriangle
Return Type: long
Method Name: findAllTriangle
Arg Types: (int, vector<int>, int, int)
Problem Statement

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

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
0)
10
{}
1750922050
8
Returns: 4
1)
7
{}
2075602252
1
Returns: 0
2)
3
{}
494950342
10
Returns: 0
3)
8
{}
70378672
1
Returns: 0
4)
6
{}
264646134
8
Returns: 4
149)
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.

150)
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.

151)
3
{2,10,16}
0
20
Returns: 1

Here we can prove that the triplet (0,1,2) is valid, so the answer is 1.

152)
2
{5,6}
0
10
Returns: 0

Since N=2, there are no triples of indices, hence the answer is zero.

153)
200000
{}
777818934
1000000000
Returns: 133390319026380

Note that B may be empty.

Submissions are judged against all 158 archived test cases, of which 10 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WeirdTriangle with a public method long long findAllTriangle(int N, vector<int> B, int seed, int MX) · 158 test cases · 2 s / 256 MB per case

Submitting as anonymous