Count The Triplets

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 0.6s

Memory limit: 64M

Problem type

Given an array of $N$ $N$ integers, the task is to count all the triplets, where a valid triplet, $(i, j, k)$ $(i, j, k)$ , has $A_i+A_j = A_k$ $A_{i} + A_{j} = A_{k}$ and $i < j$ $i < j$ . When counting triplets, only count the unique ones. Two triplets are different when, after sorting the elements corresponding to the indices, the resulting lists are different. For example, if the elements corresponding to the triplets are 1 2 3 and 3 2 1, then they are not unique, but the triplets 8 5 3 and 8 4 4 are unique. The triplet elements themselves do not necessarily have to be unique, this means that 8 4 4 can be possible, as long as the 2 4s do not have the same index.

Input Specification

The first line of input contains $N$ $N$ , denoting the size of the array.

The second line of the input contains $N$ $N$ space separated elements $A_i$ $A_{i}$ , the elements of the array.

Output Specification

Output the number of unique triplets in the array, if there are no such triplets, output -1.

Constraints

$3 \le N \le 5000$ $3 \leq N \leq 5000$

$1 \le A_i \le 10^6$ $1 \leq A_{i} \leq 10^{6}$

Sample Input 1

Copy

4
1 5 3 2

Sample Output 1

Copy

Explanation for Sample Output 1

There are $2$ $2$ such triplets, 1 2 3 and 2 3 5.

Sample Input 2

Copy

3
3 2 7

Sample Output 2

Copy

-1

Sample Input 3

Copy

6
4 1 2 3 1 2

Sample Output 3

Copy

Comments

0

YassineAllala commented on Jan. 3, 2021, 9:08 p.m.

Got segmentation errors that made me so confused, I once tried adding a "cout" instruction and it changes the result, somehow. GG for everyone

11

Togohogo1 commented on Dec. 31, 2019, 6:18 p.m.

Hints to not TLE with PY3?

10

Togohogo2 commented on Jan. 19, 2020, 5:10 p.m. ← edited →

Don't use PY3 and learn basic math.