PROSUM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Vivek Hamirwasia
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Cakewalk

PREREQUISITES:

Simple Math

PROBLEM:

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.

4 Likes
2

Take all the elements in array =2 of any size…Inequality never holds true yet we get some finite answer…

1 Like
3

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.

1 Like
4

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

5

Didn’t see your comments before I posted my answer.

6

Oh sorry, my mistake. I treat the problem as >=. I will modify it now. Thanks!

7

Oh sorry, my mistake. I treat the problem as >=. I will modify it now. Thanks!

2 Likes
8

I hope there is a test case

3
100000
0 0 0 ...
100000
1 1 1 ...
100000
2 2 2 ...

:smiley:

1 Like
9

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 ?

10

try to replace long int i,count,a,c; with long long int i,count,a,c; …

11

Well I used the following code and its giving me wrong answer. Can anyone tell me why.

 #include<stdio.h>            
 int main(){
    	int c, res, n0, n1, n2, no, tot, n, i, t, j, n22, n10o, n11, n00, n10;
        for(i=!scanf("%d", &t);i<t;i++) {
        	for(j=!scanf("%d", &n);j<n;j++) {
        		scanf("%d", &c);
        		if(c==0) n0++;
        		if(c==1) n1++;
        		if(c==2) n2++;
        	}
        	n22=((n2-1)*n2)/2;
        	n10o= (n1+n0)*(n-n0-n1);
        	n11=((n1-1)*n1)/2;
        	n00=((n0-1)*n0)/2;
        	n10=n0*n1;
        	tot=((n-1)*n)/2;
        	res=tot-n22-n10o-n11-n00-n10;
        	printf("%d\n",res);
       }
        return 0;
  }
12

But your description is different to what is your last submission - http://www.codechef.com/viewsolution/3590752

13

Please edit your code or add a link to submission (hopefully with better formatting).

Did you noticed that n*n will lead to int overflow for n up to 10^5 ?

14

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.

15

Maybe I did something wrong, but your last submission is not working at all - http://ideone.com/bvezTB

16

there was scanf("%ld",&a);, I replaced it with scanf("%lld",&a); …

17

Ok. The above got AC.But why would they need to be declared as long long int. Wouldn’t they get converted automatically when n is formulated ?

18

Getting WA ?
http://www.codechef.com/viewsolution/3619770

19

declare the variables as unsigned long long .Here is the link to the corrected code
http://www.codechef.com/viewsolution/3619806

1 Like
20

problem is in two*x…