CDW08-CODEWARS

Practice
Contest link

Author: Amit Bhardwaj
Tester: Akshat Agarwal
Editorial: Adarsh Kumar Srivastava

Difficulty:
Medium

Prerequisite:
Array , DP

Explanation & Algorithm:
We can rethink this as counting the number of equal pairs (ap,aq)=(ar,as) where p < q < r < s . To do this we loop over q from right to left and make sure we have all (ar , as ) pairs where r > q counted in a map. Then we simply iterate over p and add up the number of occurrences of each ( ap ,aq ) in the map.
For implementation details, note that we don’t actually want to use a map and make our code slower. We can just use an array of size n^2 and convert the pair
( ap,aq) to the number ap⋅n+aq since the ap are in the range [1,n] . As a bonus , even if the ap were larger than n, we could just compress them down to [1,n]
and repeat the solution.

Solution

Setter's Code

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

int main()
{
int t;
cin >> t;
while (t–)
{
int n; cin >> n;
long long ans = 0;

    vector <int> A(n,0);
    vector <long long> left(n+1,0);
   

    for (int i = 0; i < n; i++) cin >> A[i];

    for (int j = 0; j < n-2; j++)
    {
        vector <long long> right(n+1,0);
        for (int k = n-1; k > j; k--)
        {
            ans += (left[A[k]] * right[A[j]]);
            right[A[k]] ++;
        }
        left[A[j]] ++;
    }

    cout<<ans<<"\n";
}

return 0;
}

Tester's Code

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
cin>>t;
while(t–)
{
ll n;
cin>>n;
ll a[n];
ll i;
for(i=0;i<n;i++)
cin>>a[i];
ll l[n+1]={0};
ll j,k;
ll s=0;
for(j=0;j<n-2;j++)
{
ll r[n+1]={0};
for(k=n-1;k>j;k–)
{
s+=l[a[k]]*r[a[j]];
r[a[k]]++;
}
l[a[j]]++;
}
cout<<s<<endl;
}

return 0;
}