PAIRPAIN - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S.Manuj Nanthan
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given an array A containing N positive integers. Find the number of pairs (i,j) such that 1 \leq i \lt j \leq N and:
A_i + A_j \geq A_i \cdot A_j

EXPLANATION:

A_i + A_j \geq A_i \cdot A_j is equivalent to (A_i - 1)(A_j - 1) \le 1, which can only happen when:

  1. A_i = 1 or A_j = 1.
  2. A_i = 2 and A_j = 2.

We can use some inclusion-exclusion to calculate the first case quickly: that is just the number of pairs with exactly one occurence of 1 - number of pairs with exactly two occurences of 1.

TIME COMPLEXITY:

Time complexity is O(N) for each test case.

SOLUTION:

Setter's Solution
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    one=a.count(1)
    two=a.count(2)
    ans = one*(n-one)
    ans += (one*(one-1))//2
    ans +=(two*(two-1))//2
    print(ans)
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll n;
ll a[2001];
ll dp[2001];
void solve(){
	cin >> n;
	ll c1=0,c2=0;
	for(int i=1; i<=n ;i++){
		ll x;cin >> x;
		if(x==1) c1++;
		else if(x==2) c2++;
	}
	ll ans=c1*(n-c1)+c1*(c1-1)/2+c2*(c2-1)/2;
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int ones = 0, twos = 0;
        for (int i = 0; i < n; i++) {
            int u; cin >> u;
            ones += (u == 1);
            twos += (u == 2);
        }
        cout << 1LL * ones * (n - ones) + 1LL * ones * (ones - 1) / 2 + 1LL * twos * (twos - 1) / 2 << '\n';
    }
}
1 Like

can anyone tell why it is wrong???

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
int t;
cin>>t;

while(t--){
	ll n; 
	cin>>n;

	ll a[n+1];
	ll one = 0;
	ll two = 0;

	for(ll i=0 ; i<n ; i++){
		cin>>a[i];
		if(a[i]==1)
		one++;
		if(a[i]==2)
		two++;

	}

	ll ans = 0;

	if(two!=0)
	ans += two*(two-1)/2;
	if(one!=0)
	ans += (one/2)*(2*(n-1) + (1-one));           



 cout<<ans<<"\n";
	

}

return 0;

}

It’s not really clear what you’re trying to do. Your logic is wrong and your code doesn’t pass the first example case.

There are three ways to reach a solution for each pair x, y:

  1. x == 1 and y == 1. The number of solutions of this type is tri(ones - 1), where tri() is the triangular numbers function and ones is the number of ones in the set.
  2. x == 2 and y == 2. Just like case 1, the number of solutions of this type is tri(twos - 1), where twos is the number of twos in this set.
  3. x == 1 and y == anything. The number of solutions of this type is ones * not_ones, where not_ones is the number of numbers that aren’t one (ie n - one). (Rationale: each one can pair off with each not_one).

It’s well worth putting a tri() function into your template, because they crop up a lot in these problems.

1 Like

I find the question ambiguous, If I am mistaken in understanding the question please do correct me, But as I understand it the problem is asking the number of pairs of ( i , j ) not number of unique pairs of (Ai, Aj) so if a case were as such

[1, 2, 3, 2, 4, 1, 2, 1, 1] then (1,2 ), (1,3), (1,4)…(1,9) should all be valid pairs among others like (2,4), (2,7), (6,7),(6,8),(6,9) and (8,9)
and I can’t imagine why one would need inclusion exclusion principle while trying to count pairs of indices, please clarify.

1 Like

According to me in the last if one != 0 case ans should be
ans += (one/2)(2(n-one) + (one-1));

1 Like

Your approach is absolutely correct.
The only mistake you are making is in line where you are updating ans for one.

Written by you
ans += (one/2)(2(n-1) + (1-one));
Correct line
ans += ((one)(2(n-1) + (1-one)))/2;

Explanation:
Instead of dividing one by 2, you must divide the whole term by 2 after performing multiplication. It is because if no. of one’s is odd then one/2 will not give required output.

If any query remains please ask.

3 Likes

Can Anyone tell me which test cases I am missing?

here is my code
https://github.com/ParthTagalpallewar/Data-strucure-and-Algo-in-java/blob/master/PairPain.java

1 Like

where does my code wrong ??
https://www.codechef.com/viewsolution/63192389

Check if there is an overflow in Integer Multiplication.

yes thanks , after using long long int in every variable , code is accepted but i want to know why this code fails because in integer multiplication answer is stored in long long int variable so why we use every variable as long long int ???

Hey @parth1107
Thanks for asking your doubt.
Your logic is correct.
You have to just store the count of pairs in long int data type as the number of pairs can overflow in int data type.