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.

Link to the problem:

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[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.

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 :slight_smile: So that must be the bug :slight_smile:

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 :slight_smile:
So even if u got ur logic correct u would have got TLE :slight_smile: 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[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

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[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;


}
}

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

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 :confused:

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.

Also instead of

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 :confused: