HackerEarth Kriti and her Birthday Gift problem solution

In this HackerEarth Kriti and her Birthday Gift problem solution Today is Kriti's birthday but I forgot to bring a gift for her. She is very angry with me. I have an idea for a gift. She likes coding very much. Why not give her a problem to solve as her gift?

I know a problem but I am not sure whether its solvable or not.

The problem initially has N strings numbered 1 to N. The program has to answer Q queries. Each query is of the form l r S. For each query, the program has to print the number of times the string S



HackerEarth Kriti and her Birthday Gift problem solution


HackerEarth Kriti and her Birthday Gift problem solution.

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

#define CHUNK_SIZE 320
#define MAX 100005
#define MAX_STRING_SIZE 10

struct query{
long long hashValue;
pair<int,int> range;
int id;
};

map<long long,int> counts;
long long initialValues[MAX];
int answer[MAX];
query queries[MAX];

inline bool cmp(query a,query b){
a.range.first/=CHUNK_SIZE;
b.range.first/=CHUNK_SIZE;
return a.range<b.range;
}

inline long long getHashValue(char *string){
int j;
long long hashValue = 0;
for(j=0;string[j];j++){
hashValue*=27;
hashValue+=string[j]-'a';
}
for(;j<10;j++)
hashValue*27;
return hashValue;
}

int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;

char currentString[MAX_STRING_SIZE];
for(int i=0;i<n;i++){
cin>>currentString;
initialValues[i]=getHashValue(currentString);
}


int q;
cin>>q;
char queryString[MAX_STRING_SIZE];
for(int i=0;i<q;i++){
cin>>queries[i].range.first>>queries[i].range.second>>queryString;

queries[i].hashValue=getHashValue(queryString);
queries[i].range.first--;
queries[i].range.second--;
queries[i].id=i;
}

sort(queries,queries+q,cmp);

int l=0,r=-1;

for(int i=0;i<q;i++){

while(l>queries[i].range.first){
l--;
counts[initialValues[l]]++;
}
while(r<queries[i].range.second){
r++;
counts[initialValues[r]]++;
}
while(r>queries[i].range.second){
counts[initialValues[r]]--;
r--;
}
while(l<queries[i].range.first){
counts[initialValues[l]]--;
l++;
}
answer[queries[i].id]=counts[queries[i].hashValue];
}

for(int i=0;i<q;i++)
cout<<answer[i]<<"\n";
}

Second solution

#include<bits/stdc++.h>

using namespace std;

#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x,v) memset(x, v, sizeof(x))
#define sz(x) (int)x.size()
#define BLK 340

char ss[13];
map < ll , vi > M;
ll eval(char *s)
{
ll ret = 0;
int i;
for(i=0;s[i];i++)
{
assert('a' <= s[i] && s[i] <= 'z');
ret = 26*ret + s[i]-'a';
}
assert(5 <= i && i <= 10);
return ret;
}

int main()
{
int n,q,i;
scanf("%d",&n);
assert(100 <= n && n <= 100000);
for(i=1;i<=n;i++)
{
scanf("%s",ss);
M[eval(ss)].pb(i);
}
scanf("%d",&q);
assert(100 <= q && q <= 100000);
for(i=0;i<q;i++)
{
int l,r;
scanf("%d%d%s",&l,&r,ss);
assert(1 <= l && l <= n);
assert(1 <= r && r <= n);
assert(l <= r);
ll val = eval(ss);
int ans = upper_bound(all(M[val]),r) - lower_bound(all(M[val]),l);
printf("%d\n",ans);
}
return 0;
}


Post a Comment

0 Comments