//name red 2
#include<iostream>
#include<cstring>
#include<cmath>
#define l 42000
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char a[l],b[l],c[l],alpha[27]={0};
scanf("%s",a);
scanf("%s",b);
for(int j=0;j<strlen(a);j++)
{
// a[j]=tolower(a[j]);
alpha[a[j]-'0'-97]++;
}
for(int k=0;k<strlen(b);k++)
{
//b[k]=tolower(b[k]);
alpha[b[k]-'0'-97]++;
}
int flag=0;
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",c);
// cin.ignore();
for(int i=0;i<strlen(c);i++)
{
alpha[c[i]-'0'-97]--;
if((alpha[c[i]-'0'-97])<0)
{
flag=1;
break;
}
}
}
if(flag==0)
printf("YES\n");
else
printf("NO\n");
}
}
The logic I am using is: I have created an array of size 26 corresponding to all the alphabets in English language. For each letter in parent, the count is incremented. Letter ‘a’ is array[0] and ‘z’ is array[25]. Then from each of the children I decrement the alphabets. As soon as a negative number appears in the array, NO is ouput, otherwise I output YES. Could someone please clarify why this code was leading to WA.
U r condition is whether the count is negative but that is wrong u must check whether it is <= 0 I mean if count is 0 then U r short of letters to create a permutation of given strings
I also used **Exactly same logic ** and got AC So that must be the bug
My Code :
#include<iostream>
#include<string.h>
using namespace std;
typedef long int l;
int main(){
l t,p,i,j,n;
cin>>t;
while(t--){
cin>>ws;
int a[53] = {0};
string m,w;
cin>>m;
cin>>w;
m = m+w;
l lenp = m.length();
for( i = 0 ; i < lenp ; i++){
a[m[i] - 96]++;
}
cin>>n;
string c,f="";
while(n--){
cin>>c;
f = f+c;
}
l lenc = f.length();
bool chk = true;
for(i = 0 ; i < lenc; i++){
if(a[f[i] - 96] == 0) { cout<<"NO"<<endl; chk = false; break;}
else a[f[i] - 96]--;
}
if(chk)cout<<"YES"<<endl;
}
return 0;
}
It will be better if u dont use function’s like strlen inside a for loop… strlen will take linear time to find length of a character array and ur code will become inefficient
So even if u got ur logic correct u would have got TLE probably
I tried the same with cin & cin.getline. I still got WA. Plus I tried it again on my compiler now, it returns the correct answer.
I am using a MINGW compiler.
I tried different permutations of the logic. Got WA for each of them.
There is a mistake here… why ‘0’ => its ascii value is 48
so u are going into wrong array index
try alpha[c[i]-97]++
one more mistake why is alpha a char array
char a[l],b[l],c[l],alpha[27]={0};
that means maximum occurrence of any alphabet can be 127 (signed char) or 255(unsigned char)
which is overflowing for sure
Also you should look at your flag… when flag=1 and you break you still go through the for loop for the next strings which you can avoid by using flag condition in the for loop -> just an optimization, not an error
Oh man, I have a bad news for you. I was looking at your code for a while and the logic is ok, but you used char alpha[];, I replaced it with int alpha[], plus aashish_iitm’s fix.
Also instead of
alpha[c[i]-97]
you can simply use
alpha[c[i]-'a']
for better understanding (and no need for constants memoizing).
Thank you for pointing out the mistakes that I made in this particular solution.
I had tried a similar method in the 1st solution too…but even that had produced a WA. I am posting that below. Please have a look at it.
Thank you so much for all the help. Based on the answers I have received, now I am starting to wonder why my 1st solution was incorrect in the first place. Please have a look at this code too. This was my 1st attempt at the problem.
//name reduction
//codechef may
#include<iostream>
#include<cstring>
#define limit 41000
using namespace std;
int main()
{
int flag=0;
char a[limit],b[limit],c[limit];
int t,n;
cin>>t;
for(int be=0;be<t;be++)
{
cin>>a>>b;
cin.ignore();
cin>>n;
cin.ignore();
long al[26]={0};
for(int i=0;i<n;i++)
{
cin>>c;
// tolower(c);
cin.ignore();
for(int j=0;j<strlen(c);j++)
{
al[(int)c[j]-97]++;
//cout<<(int)c[j]-97;
}
}//all letters stored in al
for(int m=0;m<strlen(a);m++)
{
al[(int)a[m]-97]--;
}
for(int n=0;n<strlen(b);n++)
{
al[(int)b[n]-97]--;
}
for(int p=0;p<26;p++)
if(al[p]>0)
{
flag=1;
break;
}
if(flag==1)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
}