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;
}