Given a sequence of numbers A[1…N], find the number of pairs of i, j (i < j), such that A[i] * A[j] > A[i] + A[j].

EXPLANATION:

This problem is similar to this one occurred in OCT Long 2013. It is easy to find that if both A[i] and A[j] are greater than or equal to 2, the inequality A[i] * A[j] > A[i] + A[j] always holds. It is worth noting that, if any one of A[i] and A[j] is 0 or 1, the inequality will never hold. It is also not held for both numbers are 2.

Denote C2 as the number of 2s in the given array. And C is the number of numbers which are greater than 2.

As analyzed before, the answer is C2 * C + C * (C - 1) / 2.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

Denote C0 as the number of 0s in the given array. And C1 is the number of 1s. C2 is the number of numbers which are greater than or equal to 2. As analyzed before, the answer is C2 * (C2 - 1) / 2.

I think this part of editorial is wrong. Say, array = {2, 2, 2, 2, 2}.
C1 = 0, C2 = 5. The answer is not 10 but 0.

“It is easy to find that if both A[i] and A[j] are greater than or equal to 2, the inequality A[i] * A[j] > A[i] + A[j] always holds.” - What if both A[i] and A[j] are equal to 2?
I think the solution should count the numbers of 2s and count those greater than 2, then supposing C2 is the count of 2s and C is the count of numbers greater than 2 the solution would then be: C * C2 + C * (C - 1) / 2.

I can’t submit my solution for this problem. The algorithm I applied was to store the number of elements >=2 in a variable c and then calculate all distinct pairs using the formula c*(c-1)/2 and then subtract the number of (2,2) pairs from them.So the final formula will be c*(c-1)/2-c2*(c2-1)/2. In theory, it sounds as good as the above mentioned solution and my code gives correct output for dozens of test cases I have tried but still no AC. Can anyone point out the error ?

Sorry to have mislead you. What I have done is I calculated the 1’s and 0’s in c. Then I reduced n(the total no. of elements) by c.So,now n is the total no. of elements >=2. And count is the number of 2’s. Then i applied the formula n*(n-1)/2 - count*(count-1)/2. Also, replacing by long long int didn’t work.