NPLQ19F ICPC Preparation - Editorial

editorial
, , ,
1

PROBLEM LINK:
[https://www.codechef.com/NPLQ2019/problems/NPLQ19F]
Contest
Practice

Author: rishigurjar
Editorialist: rishigurjar

DIFFICULTY:
Medium

PREREQUISITES:
Merge sort tree, segment tree

PROBLEM:
For each query find the number of distinct anagrams in given range L to R.

EXPLANATION:
If we observe the given constraints on characters (‘a’<=s[i]<=‘e’) and length of string (|s|<=15) we can easily map each string to some integer. We can assign prime numbers to each character ( here {2,3,5,7,11} for characters ‘a’ to ‘e’) and then for a string we can get the integer by multiplication of all prime numbers assigned to each character in the string. Now we can easily say that if two strings are anagrams then they will get same mapped integers. For eg. we have two strings s1=“abbc” and s2=“babc” (s1 and s2 are anagrams) then mapped integer for s1 would be i1=2*3*3*5 = 90 and for s2 it would be i2=3*2*3*5 = 90.

Now the problem can be reduced easily to finding the number of distinct elements in given range L to R. Now this problem can be solved using following logic -

For each index i find the next index which is having same element as i or if there is no such element then put it n (store the values in some array B). This can be done easily by keeping a map and traverse the array from right to left (have a look at the code for more clearification ).
Now for a given query L to R our result will include the elements from array B which lies in L to R and having values greater than R (because if some element is having values less than or equal to R then it means that it is repeating itself in the given range so we don’t include that in result).

Now to query this part efficiently we can use merge sort tree. Build a merge sort tree on array B and then query according to the above logic. Each query will take O(log^2) .

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 1e15
#define ll long long int
#define s(t) scanf("%d",&t)
#define p(t) printf("%d\n",t)
#define pb push_back
#define f(t) for(int i=0;i<t;i++)
#define F first
#define S second
#define all(t) t.begin(),t.end()

using namespace std;
struct node{
int x;
int y;
};
const int N = 1e5;
ll n;
vector<ll> t[2 * N];

vector<ll> merge(vector<ll> a, vector<ll> b)
{
ll i=0,j=0;
vector<ll> c;
while(i<a.size()&&j<b.size())
{
if(a[i]<b[j])
{
c.pb(a[i]);
i++;
}
else
{
c.pb(b[j]);
j++;
}
}
while(i<a.size())
{
c.pb(a[i]);
i++;
}
while(j<b.size())
{
c.pb(b[j]);
j++;
}
return c;
}

ll find(vector<ll> v, ll lim)
{
ll ind = (lower_bound(all(v), lim)-v.begin());
return v.size()-ind;
}
void build() {
for (int i = n - 1; i > 0; --i)
t[i] = merge(t[i<<1],t[i<<1|1]);
}

int query(int l, int r) {
ll res = 0;
ll R=r;
for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if (l&1) res += find(t[l++],R);
if (r&1) res += find(t[--r],R);
}
return res;
}

int main()
{

cin>>n;
ll a[n];
ll p[]={2,3,5,7,11};
f(n)
{
string s;
cin>>s;
ll val=1;
for(int j=0;j<s.length();j++)
val*=p[s[j]-'a'];
a[i]=val;
}
map<ll, ll> m;
ll b[n];
ll mx=n;
for(int i=n-1;i>=0;i--)
{
if(m.find(a[i])==m.end())
{
b[i]=mx;
}
else
{
b[i]=m[a[i]];
}
m[a[i]]=i;
}

for (int i = 0; i < n; ++i)
t[n+i].pb(b[i]);
  build();
 
  int q;
  cin>>q;
  while(q--)
  {
  int l,r;
  s(l);
  s(r);
  l--;r--;
  int x=query(l,r+1);
  p(x);
}
return 0;
}
2 Likes