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].
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.
“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.