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


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