GOODPAIRS-Editorial

PROBLEM LINK:

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

Setter: Utkarsh Gupta
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh

DIFFICULTY:

1469

PREREQUISITES:

Map data structure

PROBLEM:

You are given 2 arrays A and B of length N each. Determine the number of good pairs.

A pair (i,j) is said to be good if:

  • i \lt j
  • A_i = B_j
  • A_j = B_i

EXPLANATION:

Iterate over the arrays A and B from j=1 to N and keep count of the pair formed by (A_j,B_j). Let us now count the number of indices i for each index j (i<j) such that (i,j) form a good pair.
If (i,j) form a good pair then :
A_j=B_i and B_j=A_i;
This means the pair (A_i,B_i) is same as the pair (B_j,A_j);
Thus for each j add count of the pair (B_j,A_j) to the answer and increase the count of (A_j,B_j) by 1

TIME COMPLEXITY:

O(Nlog(N)) for each test case.

SOLUTION:

Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
int sumN=0;
void solve()
{
    int n=readInt(1,100000,'\n');
    sumN+=n;
    assert(sumN<=200000);
    int A[n+1]={0}, B[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        int c;
        if(i<n)
            c=readInt(1,1000000000,' ');
        else
            c=readInt(1,1000000000,'\n');
        A[i]=c;
    }
    for(int i=1;i<=n;i++)
    {
        int c;
        if(i<n)
            c=readInt(1,1000000000,' ');
        else
            c=readInt(1,1000000000,'\n');
        B[i]=c;
    }
    map <pair<ll,ll>,ll> cnt;
    ll ans=0;
    for(int i=1;i<=n;i++)
        cnt[mp(A[i],B[i])]++;
    for(int i=1;i<=n;i++)
    {
        cnt[mp(A[i],B[i])]--;
        ans+=cnt[mp(B[i],A[i])];
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int T=readInt(1,1000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n;
    cin >> n;
    int a[n], b[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    map<pll, ll> cnt;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        pll p = {b[i], a[i]};
        ans += cnt[p];
        p = {p.S, p.F};
        cnt[p]++;
    }
    cout << ans << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
3 Likes

I tried without map, was continuously getting TLEs

7 Likes

I think this should be "the pair A_j, B_i is same as A_i, B_j.

2 Likes

Can someone help me with my solution.
I was trying to solve the problem in this way but i am getting WA.
if A_i = B_j and A_j = B_i. We can easily say the A[i]+A[j] = B[i] + B[j]
or (A[i] - B[i]) + (A[j] - B[j]) = 0. Hence if A[i] - B[i] = D[i] . We just have to find pairs where i < j and D[j] = -D[i].
This is my solution.

Using MAP

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int n, c = 0;
    std::cin >> n;
    std::vector <int> a(n), b(n);
    std::map <std::pair<int,int>,int> u;
    for(auto &i:a)
        std::cin >> i;
    for(auto &i:b)
        std::cin >> i;
    for(int i=0; i<n; i++){
        c += u[{a[i], b[i]}];
        u[{b[i], a[i]}]++;
    }
    std::cout << c << "\n";
}
     
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 0;
    std::cin >> t;
    while(t--){
        solve();
    }
}
4 Likes

Your logic of writing A[i] = B[j] and A[j] = B[i] as A[i]+A[j] = B[i] + B[j] is wrong. It does not imply that A[i] = B[j] and A[j] = B[i] always. For example it fails when A[i] = 2 , A[j] =4, B[i] = 3 and B[j] = 3.
Here, A[i] != B[j] and A[j] != B[i] but A[i] + A[j] = B[i] + B[j] is satisfied.

1 Like

Using unordered_map shows error for pair<int,int> , but 'map
’ works fine. Why is it so?

I was able to reach to the solution point but was getting the TLE error. If possible, can anyone provide a solution in C# for this?

This is because unordered_map uses a hash table so needs a hash func defined for the key. The std lib comes with predefined string, int, … (basic type) hash function. but no hash func for a pair. Hence it does not work. But map works because it uses a balanced bst so it has no need for hash func and the tree nodes can store anything.

My approach is alright.
But, I’m getting TLE in the 3rd test case.
(All others are AC)

Could you please help me get it AC? :frowning: :pleading_face:
Link- Solution: 64843334 | CodeChef

@devendra7700

in the code uve written where have u accounted for indices where i>j can u please explain that?

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner ob=new Scanner(System.in);
int t=ob.nextInt();
while(t–>0){
int n=ob.nextInt();
int a[]=new int[n];
int b[]=new int[n];
for(int i=0;i<n;i++)
a[i]=ob.nextInt();
for(int i=0;i<n;i++)
b[i]=ob.nextInt();

	    Map<String,Integer> hm=new HashMap<>();
	    for(int i=0;i<n;i++){
	        if(hm.containsKey(a[i]+" "+b[i])){
	            int nf=hm.get(a[i]+" "+b[i])+1;
	            hm.put(a[i]+" "+b[i],nf);
	        }
	        else
	            hm.put(a[i]+" "+b[i],1);
	    }
	    
	    long ans=0;
	    
	    for(int i=0;i<n;i++){
	        if(hm.containsKey(b[i]+" "+a[i])){
	            int c=hm.get(a[i]+" "+b[i]);
	            int d=hm.get(b[i]+" "+a[i]);
	            
	            if( a[i]==b[i] )
	                ans+=c*(c-1)/2;
	            else
	                ans+=c*d;
	            
	            hm.put(a[i]+" "+b[i],0);
	            hm.put(b[i]+" "+a[i],0);
	        }
	    }
	   System.out.println(ans);
	}
}

}

why is test case 3 failing in by this approach?

Hi,
The return value can be long also. Declare c, d as long and execute(or cast to long while multiplying). It will pass all the test cases
Below is my solution where it has passed all the testcases with same approach.
https://www.codechef.com/viewsolution/65476340

Thanks
Manjunath