Hello Everyone,
I found problem D, zigzags, of Educational Codeforces Round 94, very interesting.
So I thought I should share my approach for this question.
In case you haven’t read the problem statement. You can read it here :
-
PROBLEM STATEMENT :
The question asks us to count the number of tuples(i, j, k, l) in the given array such that i < j < k < l and the given condition holds true :a[i] = a[k] and a[j] = a[l]
-
EXPLANATION :
One way to approach this problem is that we can fix j and k and then for every j and k we can find the number of i and l which we can select.
So, for this we will try to make a pre_hash[][] and suf_hash[][] in which we will store the frequency of every element till i.
As the value of n(size of the array) can go till 3000 and every element in the array will be smaller than 3000, we can maintain 2-d array of size of 3000 and 3000.
In pre_hash[][], we will store the frequency of each element till i from left to right.
In suf_hash[][]. we will store the frequency of each element till i from right to left.Now, if we fix j and k, then the ans for that particular j and k will be the number of i and l which we can select such that a[i] = a[k] and i < j and a[l] = a[j] and l > k.
So, basically our ans will be :ans += pre_hash[i - 1][a[j]] * suf_hash[j + 1][a[i]]; (for every j and k)
-
CREATING pre_hash[][]
We can create pre_hash[][] like this :
map<int, int> mp;
for(int i = 0; i < n; ++i){
mp[a[i]]++;
pre_hash[i][a[i]] = mp[a[i]];
for(int j = i + 1; j < n; ++j) pre_hash[j][a[i]] = mp[a[i]];
}
- CREATING suf_hash[][]
map<int, int> mpp;
for(int i = n - 1; i >= 0; --i){
mpp[a[i]]++;
suf_hash[i][a[i]] = mpp[a[i]];
for(int j = i - 1; j >= 0; --j)
suf_hash[j][a[i]] = mpp[a[i]];
}
My solution :
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define vii vector<ll>
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7, N = 3003;
ll pre_hash[N][N], suf_hash[N][N];
int main(){
fast;
ll t;
cin >> t;
while(t--){
ll n;
cin >> n;
ll a[n];
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
pre_hash[i][j] = 0;
suf_hash[i][j] = 0;
}
}
for(int i = 0; i < n; ++i)
cin >> a[i];
map<int, int> mp, mpp;
for(int i = 0; i < n; ++i){
mp[a[i]]++;
pre_hash[i][a[i]] = mp[a[i]];
for(int j = i + 1; j < n; ++j) pre_hash[j][a[i]] = mp[a[i]];
}
for(int i = n - 1; i >= 0; --i){
mpp[a[i]]++;
suf_hash[i][a[i]] = mpp[a[i]];
for(int j = i - 1; j >= 0; --j) suf_hash[j][a[i]] = mpp[a[i]];
}
ll ans = 0;
for(int i = 1; i < n - 2; ++i){
for(int j = n - 2; j > i; --j){
// cout << a[i] << " " << a[j] << " " << pre_hash[i - 1][a[j]] * suf_hash[j + 1][a[i]] << endl;
ans += (pre_hash[i - 1][a[j]] * suf_hash[j + 1][a[i]]);
}
}
cout << ans << "\n";
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= n; ++j)
pre_hash[i][j] = 0, suf_hash[i][j] = 0;
}
cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
return 0;
}
Feel free to ask any queries