[Solution] Pair Pain solution codechef

Pair Pain solution codechef – You are given an array AA containing NN positive integers. Find the number of pairs (i,j)(i,j) such that 1i<jN1≤i<j≤N and:

[Solution] Pair Pain solution codechef

Ai+AjAiAjAi+Aj≥Ai⋅Aj

Input Format

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains an integer NN.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, output on a new line the required answer.

[Solution] Pair Pain solution codechef

  • 1T10001≤T≤1000
  • 2N21052≤N≤2⋅105
  • 1Ai1061≤Ai≤106
  • Sum of NN over all cases won’t exceed 21052⋅105

Sample Input 1 

2
3
1 3 4
5
2 3 4 5 6

Sample Output 1 

2
0

Pair Pain solution Explanation

Test case 11: The two pairs are (1,2)(1,2) and (1,3)(1,3), because:

  • A1+A2=4>3=A1A2A1+A2=4>3=A1⋅A2
  • A1+A3=5>4=A1A3A1+A3=5>4=A1⋅A3

Test case 22: No pairs satisfy the condition.

Leave a Comment