 # Name reduction Query( May Challenge)

I submitted this code and got WA. Could someone please tell me why I am getting WA despite it working perfectly in my computer.

Name reduction

Here is my code:

``````//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={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 and ‘z’ is array. 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.

3 Likes

For input from problem statement it returns NO, NO, NO…

Problem probably is, that scanf reads only one word instead of whole line as you probably expect…

1 Like

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 = {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

alpha[c[i]-‘0’-97]–;

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={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

here is your code corrected accepted

http://www.codechef.com/viewsolution/2165148

spend some time on what data types to use before coding and u will have fun

4 Likes

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={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;

}
}``````

+1 because of nice description, it would be perfect if everyone describe the problem and approach like you did 2 Likes

…u must check whether it is <= 0…

I’m afraid that this is not correct. In your code you are decreasing after check, while piy9 is decreasing before, so his condition is ok.

1 Like

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.

You can see all my submissions here.

This is very frustrating Seriously, rare guys write code intended properly and with a description of how they achieved that.

1 Like

@piy9 >> Why play with negatives when you can easily go off with positive numbers? http://www.codechef.com/viewsolution/2083108

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.

``````alpha[c[i]-97]
``````

you can simply use

``````alpha[c[i]-'a']
``````

for better understanding (and no need for constants memoizing).

http://www.codechef.com/viewsolution/2165213

2 Likes

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.

you are not reseting the flag for test case - once it’s set to 1 it is 1 for all test cases, see http://ideone.com/rebxME

1 Like

OH god!!! Thank you so much. I can’t believe I made that error 