PROBLEM CODE-LAPIN

getting WA though getting right answers for different test cases in my compiler.if i m missing anything plz explain!!

Can you please explain your process to find lapindromes ?
So that i can help you

I have seperated the two halves in two arrays and then compare both the arrays

Nice, You are on a proper track but have you consider 2 different conditions on input string??

Condition 1 : When the lenght of the Input String is Even

Condition 2 : When the lenght of the input String is Odd.

When the Length of the String is even then it won’t create any problem for you but in case of odd you have to skipped middle element.

Consider string “rotor” here the middle element ‘t’ must be neglected and rest of the 2 part of the string are to be compared i.e. Part 1 of string : " ro" is to be compared with second part of the string : “or”.
And as both are same so the given string “rotor” is a lapindrome

Let me know if there is other error other then this condition.

Yes i have checked the even and odd condition and as stated earlier checked for no. Of test cases .but on codechef it is showing WA.
what could i miss!!

Can you please show me your code?
Then i can point out your error

Remember to sort them after dividing

I think when you are comparing two arrays you are comparing in order .
But order can be different in both array .
You should check frequencies of each character.

#include<stdio.h>
#include<string.h>
int main()
{
long long int t;
scanf("%lld",&t);
while(t–)
{ long long int mid,i,j,k=0,flag=0;
char a1[10000],a2[10000];
char str[10000];
scanf("%s",str);
mid=strlen(str)/2;
if(strlen(str)&1==1)
{
for(i=0;i<mid;i++)
{
a1[i]=str[i];
}
for(j=mid+1;j<strlen(str);j++)
{
a2[k]=str[j];
k++;
}

    }
    else
    {
        for(i=0;i<mid;i++)
            a1[i]=str[i];
        for(j=mid;j<strlen(str);j++)
        {
            a2[k]=str[j];
            k++;
        }
    }
  //  for(i=0;i<strlen(a1);i++)
    //    printf("%c\n",a2[i]);

    for(i=0;i<strlen(a1);i++)
    {
        for(j=0;j<strlen(a2);j++)
        {
            if(a1[i]==a2[j])
            {
               a2[j]='1';
              flag++;
              break;
            }


        }
    }
    if(flag==strlen(a1))
        printf("YES\n");

    else
        printf("NO\n");
        //printf("%d",flag);


}
return 0;

}

You are unnecessarily making it complex. You can answer it in a simple manner.

Take an hash array of size 26 and assigned the whole array equal to zero
int hash[26] = {0}

Now When you traverse through the first half of the string, count the frequency of the letters using the hash array i.e increment the array i.e increment it (++)

And afterwards when you are traversing the second half of the string then decrease the count of the frequency of the letters that are present in the second half of the string i.e decrement using (- -)

Atlast if all the values of the hash array are zero then the string is a lapindrome and if not zero then the string is not a lapindrome

Don’t count the frequency of the middle element in the odd lenght string

Let me know if you still don’t get it

I am too getting WA on my Solution.

I am using two unordered_map(s) to store ,both, the characters and their counts , and then using operator ‘==’ to compare if they r equal or not.

Also i’m handling odd and even length string part correctly.

still getting WAs on test cases , though my code runs very correctly on my machine.

Code :-

#include<bits/stdc++.h>
using namespace std;

int main()
{

int T;
cin >> T;

while(T–){
ios::sync_with_stdio(false);
cin.tie(NULL);

int i,j;
string s;
getline(cin,s);
int len = s.length();
int low,high;

unordered_map<char,int> umap1,umap2;

if(len%2 == 0){
  low = len/2;
  high = len/2-1;
}

else{
  low = len/2+1;
  high = len/2-1;
}

for(i=0; i<=high; i++){
  if(umap1.find(s[i]) == umap1.end())
    umap1.insert({s[i],1});
  else
    umap1[s[i]]++;
}

for(j=low; j<len; j++){
  if(umap2.find(s[j]) == umap2.end())
    umap2.insert({s[j],1});
  else
    umap2[s[j]]++;
}

if(umap1 == umap2)
  cout << "YES" << endl;
else
  cout << "NO" << endl;

}
return 0;

}

PS- I know the single array of size 26 approach is my more neat , but , still i don’t get it…why my code is giving WA ??

You can have a look at the following C++ code: https://github.com/strikersps/Competitive-Programming/blob/master/Code-Chef/Lapindromes/lapindromes.cpp

I’m clearly getting your code and logic , which is really good , but then the classic question why my code is not working ? where is the error ?

Also… when i do , what in your code is macro FAST_IO(0), inside the outer loop (exactly where u have used…), my code takes 1 less input ? can u make me understand, in short, why ? since this FAST_IO thing is gonna be very repetitive in solving all the problems !!!

How to improve this problem ?

I have been debugging your code for the past 90 minutes and i can’t find anything wrong with it, I even modified areas of “doubt” and still gets WA. I think maybe you (and I) should let this go :smiley:

I couldn’t let it go XD

but i finally found it! although i don’t know exactly how it works…

but here is the answer

remove
ios::sync_with_stdio(false);
cin.tie(NULL);

from the while loop, move them directly under int main(){

and use cin >> s;
instead of getline(cin, s);

nearly 2 hours of work xD

goodnight it is 1 AM :smiley:

1 Like

now i know why , getline gets out of sync with cin, just as scanf :slight_smile:

Refer to this post: https://stackoverflow.com/q/31162367/12210908.
First understand what std : : ios : : sync_with_stdio(0) and std : : cin.tie(NULL) does, then you can find out the bug in your program.

Hey @mwaheed, thank you so much bhai…u took your time to do the dirty work of finding the bug…i too get it ( finally !)… this I/O stream sync thing between c nd c++ , though makes , code efficient to take inputs and make code run fast…but my god… needs to be clearly understood…ufff :stuck_out_tongue:

Again…thank you so so much for your precious time…

1 Like

you should refer to this too…https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio