Probelm D : Zigzags Codeforces

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 :
https://codeforces.com/contest/1400/problem/D

  • 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 :slight_smile:

2 Likes

Another alternate solution can be not creating a suf_hash and pre_hash explicitly, we can compute them during the process.
Code is Here ->
#define ll long long
int main()
{

int n;
cin>>n;
vector<int> arr(n+1);
for(int i=1;i<=n;i++)
cin>>arr[i];
map<int,int> leftcount;
ll int answer=0;
for(int l=1;l<=n;l++){
	int count=0;
	for(int k=n;k>=l+1;k--){			 
		 answer+= leftcount[arr[k]]*count;
		  if(arr[k]==arr[l])
		 count++;

	}
	leftcount[arr[l]]++;
}
cout<<answer<<endl;
return 0;

}

1 Like

I tried coding the similar approach, can you please help what’s wrong in my code, its failing on test case-3 and afterwards-

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

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int arr[n];
        for(int i=0; i<n; i++){
            cin >> arr[i];
        }

        // freqleft[x][i]->frequency of element x in array till index i(including index i)-
        int freqLeft[3003][n]={{}};
        // freqRight[x][i]->frequency of element x in array after index i(including index i)-
        int freqRight[3003][n]={{}};

        for(int i=0; i<3003; i++){
            for(int j=0; j<n; j++){
                if(j-1>=0) freqLeft[i][j]+=freqLeft[i][j-1];
                if(arr[j]==i) freqLeft[i][j]+=1;    
            }
        }

        for(int i=0; i<3003; i++){
            for(int j=n-1; j>=0; j--){
                if(j+1<n) freqRight[i][j]+=freqRight[i][j+1];
                if(arr[j]==i) freqRight[i][j]+=1;
            }
        }

        int ans = 0;
        for(int i=1; i<n-2; i++){
            for(int j=i+1; j<n-1; j++){
                ans+=((freqLeft[arr[j]][i-1]*freqRight[arr[i]][j+1]));
            }
        }
        cout<<ans<<'\n';
    }    

    return 0;
}

Hello @pakalupapito,
Initialize freqLeft and freqRight from 0.
You can use :

memset(freqRight, 0,sizeof(freqRight)) ;
memset(freqLeft,  0, sizeof(freqLeft)) ;

Also u have taken ans as int. Int will overflow so use long long int :slight_smile:

1 Like

Thank you it worked. I thought {{}} initialize 2d array with all 0 values, I verified and it did but seems like it won’t work for big 2d arrays.