Header Ad

HackerEarth Fashion Line problem solution

In this HackerEarth Fashion Line problem solution, Rachel works at a big fashion organization. There is a big event coming up and she has to select dresses for an exhibition.

She has N dresses numbered 1 to N. There is a total of 62 types of dresses, each represented by a different alphanumeric character (a-z, A-Z, 0-9). The N dresses are represented by a string S of length N of alphanumeric characters. The ith character of S denotes the type of the ith dress. Rachel will select two integers, A and B such that 1 <= A <= B <= N and take the dresses numbered from A to B to the exhibition.

Out of the 62 dress types, K dress types are special. Find the number of values of A and B possible such that the total number of special dresses of any type selected is at least L and at most R.


HackerEarth Fashion Line problem solution


HackerEarth Fashion Line problem solution.

#include<bits/stdc++.h>
using namespace std;
int getCharId(char ch)
{
if(ch>='a' && ch<='z')
return ch-'a';
else if(ch>='A' && ch<='Z')
return ch-'A'+26;
else if(ch>='0' && ch<='9')
return ch-'0'+52;
else
return -1;
}
int main()
{
int T;
cin>>T;
assert(1<=T && T<=100);
while(T--)
{
char str[10001],special[10001];
int N,mark[62]={0},K,i,L,R;
cin>>N>>K>>L>>R;
assert(1<=N && N<=10000 && 1<=K && K<=62 && 0<=L && L<=N && 0<=R && R<=N && L<=R);
cin>>str>>special;
assert(strlen(str)==N);
assert(strlen(special)==K);
for(i=0;i<K;i++)
{
mark[getCharId(special[i])]=1;
}
int next[100001],next_c=0;
int len=strlen(str);
for(i=0;i<len;i++)
{
if(mark[getCharId(str[i])]==1)
{
next[next_c]=i;
next_c++;
}
}
long long ans=0,next_i=0;
for(i=0;i<len;i++)
{

if(next_i+L-1>=next_c)
break;

int till1=i;
if(L!=0)
till1=next[next_i+L-1];
int till2=len-1;
if(next_i+R<next_c)
{
till2=next[next_i+R]-1;
}

if(till1<=till2)
{
ans+=(till2-till1+1);
}
if(mark[getCharId(str[i])]==1)
next_i++;
}
cout<<ans<<endl;
}
return 0;
}


Second solution

#include <bits/stdc++.h>

using namespace std;

bool chk[252];
int dp[10002];

int main()
{
int t,n,m,l,r;
string s,p;

int ans;

cin >> t;
assert(t>=1&&t<=100);
while ( t-- ) {
memset(chk, false, sizeof(chk));
cin >> n >> m >> l >> r;
assert(n>=1&&n<=10000);
assert(m>=1&&m<=62);
cin >> s >> p;
assert(s.size() == n);
assert(p.size() == m);
assert(l>=0&&l<=n);
assert(r>=0&&r<=n);
assert(l<=r);
for ( int i = 0; i < p.size(); i++ ) {
assert(p[i]>=0&&p[i]<=251);
chk[p[i]] = true;
}
dp[0] = 0;
ans = 0;
for ( int i = 1; i <= n; i++ ) {
assert(s[i-1]>=0&&s[i-1]<=251);
dp[i] = dp[i-1] + chk[s[i-1]];
}
for ( int i = 1; i <= n; i++ ) {
int lf,rt,md,fs=-1,sc=n+1;
lf = i, rt = n, md = -1;
while ( lf <= rt ) {
md = (lf+rt)/2;
int val = dp[md] - dp[i-1];
if ( val >= l ) {
fs = md;
rt = md-1;
}
else if ( val < l ) lf = md+1;
}
if ( fs == -1 ) continue;
lf = i,rt = n, md = -1;
while ( lf <= rt ) {
md = (lf+rt)/2;
int val = dp[md] - dp[i-1];
if ( val > r ) {
sc = md;
rt = md-1;
}
else lf = md+1;
}
ans += sc-fs;
}
cout << ans << endl;
}
return 0;
}

Post a Comment

0 Comments