HackerEarth Shubham and Subarrays problem solution

In this HackerEarth Shubham and Subarrays problem solution You are given an array consisting of n integer numbers a1,a2..an. Two subarrays  ([l1,r1]) (1 <= l1 <= r1 <= n) and [l2,r2] (1 < l2 <= r2 <= n) are considered the same if they have the same "special set" of numbers. Output the number of distinct subarrays.

Note: A "special set" of numbers is a set of unique numbers sorted in increasing order.For example,the "special set" corresponding to the numbers [5,2,7,2,5,9] is [2,5,7,9].

HackerEarth Shubham and Subarrays problem solution.

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 1005

ll arr[maxn],power1[maxn],power2[maxn],seen[maxn],base1=127,base2=129,mod1=mod,mod2=mod+2;
set<pair<ll,ll> >s;

inline ll add(ll x,ll y,ll modulus)
{
    x+=y;
    if(x>=modulus)
    x-=modulus;
    return x;
}
inline ll mul(ll x,ll y,ll modulus)
{
    return (x*y)%modulus;
}
int main()
{
    boost1;boost2;
    ll i,j,n,x,y,hash_val1,hash_val2;
    power1[0]=1;
    power2[0]=1;
    for(i=1;i<=1000;i++)
    {
        power1[i]=mul(power1[i-1],base1,mod1);
        power2[i]=mul(power2[i-1],base2,mod2);
    }
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>arr[i];
    for(i=1;i<=n;i++)
    {
        hash_val1=0;
        hash_val2=0;
        for(j=i;j<=n;j++)
        {
            if(!seen[arr[j]])
            {
                hash_val1=add(hash_val1,power1[arr[j]],mod1);
                hash_val2=add(hash_val2,power2[arr[j]],mod2);
            }
            seen[arr[j]]=1;
            s.insert({hash_val1,hash_val2});
        }
        for(j=i;j<=n;j++)
        seen[arr[j]]=0;
    }
    cout<<s.size();
    return 0;
}

Second solution

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

#define ll long long
#define ii pair<int, int>
#define ff first 
#define ss second 

int temp[1005];

int main(){
    int i, j, n, base[2], mod[2], arr[1005], ans = 0;
    int pwrs[2][1005];
    base[0] = 31;   mod[0] = 999999937;
    base[1] = 37;   mod[1] = 999999929;

    unordered_map<ll, bool> globe;

    pwrs[0][0] = 1;
    pwrs[1][0] = 1;

    for(i = 1; i <= 1000; i++){
        pwrs[0][i] = (1ll * pwrs[0][i - 1] * base[0]) % mod[0];
        pwrs[1][i] = (1ll * pwrs[1][i - 1] * base[1]) % mod[1];
    }

    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    for(i = 0; i < n; i++){
        ii curr = {0, 0};
        for(j = i; j < n; j++){
            if(temp[arr[j]] != 0)
                continue;
            temp[arr[j]] = 1;
            curr.ff = (curr.ff + pwrs[0][arr[j]]) % mod[0];
            curr.ss = (curr.ss + pwrs[1][arr[j]]) % mod[1];
            if(globe[((1ll * curr.ff) << 30) + curr.ss] != 0)
                continue;
            ans++;
            globe[((1ll * curr.ff) << 30) + curr.ss] = 1;
        }
        for(j = i; j < n; j++)
            temp[arr[j]] = 0;
    }
    printf("%d\n", ans);

    return 0;
}