LAPIN - Editorial

Help Me please !!

I am unable to find and rectify the error in the following :

#include <bits/stdc++.h>
#include <string>

using namespace std;

#define N 1000000007
#define ll long long



int main()
{
ll t;
cin>>t;
while(t--)
{

    string s;
    cin>>s;
    ll l;
    if(s.length()%2==0)
      {
        l=s.length()/2;
      }
else{
    l=(s.length()-1)/2;
}
char a1[l],a2[l];

if(s.length()%2==0)
{
    for(int i=0;i<l;i++)
{
    a1[i]=s[i];
    a2[i]=s[i+l];
}
}
else{
    for(int i=0;i<l;i++)
{
    a1[i]=s[i];
    a2[i]=s[i+l+1];
}
}

a1[l]='\0';
a2[l]='\0';
sort(a1,a1+l);
sort(a2,a2+l);
bool isSame=true;
for(int i=0;i<l;i++)
{
    if(a1[i]!=a2[i])
    {
        isSame=false;
        break;
    }
}
if(isSame)
{
    cout<<"YES\n";
}
else{
    cout<<"NO\n";
}

}

return 0;

}

It is satisfying all test cases but getting a WA.

https://www.codechef.com/viewsolution/19355962

Would appreicate some help here! Using similar logic. Works with multiple test cases on other online compilers. Char array is 1 more than 1000 for ‘\0’. specially added condition when s<1. getting WA with or without the s condition. Please help!

https://www.codechef.com/viewsolution/19381347 here’s the link in python. Still wont work. The one with editorial logic worked but this doesnt even with multiple testcases on the codechef compiler. Pleas help!!!

want a cookie :P…why complicate a cake-walk !

4 Likes

@v_akshay , that will increase the complexity from O(n) to O(nlogn)

Oh @v_akshay, nice!

So, basically I could rewrite isLapin as follows:


isLapin(string S)
{
    int len = S.length();
    int r1 = len/2, l2 = (len+1)/2;
    sort(S.begin(), S.begin() + r1);
    sort(S.begin() + l2, S.end());
    return S.substr(0, r1) == S.substr(l2);
}

@spandanpathak, surely this can’t be called “complicating” :stuck_out_tongue:

3 Likes

@sumanth232 , well, I know that but we have |S|<=1000, so O(nlogn) is well under time constraints :slight_smile: .
@pragrame , thanks :slight_smile: , and perfect implementation :slight_smile:

Here is your AC code with array size increased. http://www.codechef.com/viewsolution/2279176

3 Likes

try this:
1
abac

@insaynasasin imho, you tried to convert chars in your string array to ints. try left[arr[i]-‘a’], right[arr[i]-‘a’]

@garakchy but what is the difference between the two formats?

@garakchy no luck, it is still giving the right answers for the given testcases but on submission, its a wa

@vytenis
my code is saying yes for the given string
and that is worng
i get the point

was trying since yesterday, lol, and i just got ac on the problem.

and i used memcmp, that is a bit faster than every array index comparison imho, try that also @insaynasasin

why is this wrong

    #include<iostream>
    #include<string>
   #include<vector>
   using namespace std;

int main()
{
    int t;
    cin>>t;
    vector<string> ans;

    while(t--)
    {
        string str;
        cin>>str;

        while(str.length()>1)
        {
            int len = str.length();
            int last_of_first_half;
            int first_of_second_half;
            int sum1,sum2;
            sum1=sum2=0;

            char ch = str[0];
            if(len%2!=0)
            {
                last_of_first_half = len/2 -1 ;
                first_of_second_half = len/2 +1 ;
            }
            else
            {
                last_of_first_half = len/2 -1 ;
                first_of_second_half = len/2  ;
            }
            string temp="";
           for(int i=0;i<=last_of_first_half;i++)
           {
               if(str[i]==ch)
                sum1++;
               else
               {
                   temp+=str[i];
               }
           }
            for(int j=first_of_second_half;j<len;j++)
            {
               if(str[j]==ch)
                sum2++;
               else
               {
                   temp+=str[j];
               }
            }
            if(sum1!=sum2)
                break;
            else
                str=temp;
        }

        if(str.length()<2)
            ans.push_back("YES");
        else
            ans.push_back("NO");
    }

    for(auto i=ans.begin();i!=ans.end();i++)
        cout<<*i<<"\n";
    return 0;
}

#include
#include
using namespace std;
int main()
{
int T;
cin>>T;
for(int i=0;i<T;i++)
{ int half;
int count=0;

    string s;
    cin>>s;
    
    
    int len=s.length();
    if(len%2 == 0)
    {
        half=len/2;
         string s1[half];
    string s2[half];
    for(int j=0;j<half;j++)
    {
        s1[j]=s[j];
        s2[j]=s[len-j-1];
        
    }
    for(int j=0;j<half;j++)
    {for(int k=0;k<half;k++)
    {
        if(s1[j]==s2[k])
        {
            count++;
            s1[j]=j;
            s2[k]=j;
            
            
        }
       
        
    }}

    
      if(count==half)
        {
            cout<<"YES";
            
        }
     
        else
        {cout<<"NO";}
        
       cout<<endl;
    
}
     
    
    else
    {
    
      half=(len+1) /2;
      
    
    string s1[half-1];
    string s2[half-1];
    for(int j=0;j<half-1;j++)
    {
        s1[j]=s[j];
        s2[j]=s[len-j-1];
        
    }
    for(int j=0;j<half-1;j++)
    {for(int k=0;k<half-1;k++)
    {
        if(s1[j]==s2[k])
        {
            count++;
            s1[j]=j;
            s2[k]=j;
            
            
        }
     
        
    }}

    
      if(count==(half-1))
        {
            cout<<"YES";
            
        }
     
        else
        {cout<<"NO";}
        
       cout<<endl;
    
}
}

return 0;

}

i used different approach , no sorting no array declaration, is this best one compared to other ?
https://www.codechef.com/viewsolution/27532994

My code gets compiled and run successfully but it doesnt get accepted during submission
Can you please point out the reason why it is like that from the following code ?
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
String ans="";
while(T>0){
String b=br.readLine();
ans+=solve(b);
T–;
}
System.out.print(ans);
}
static String solve(String x){
int len=x.length();
String com1=null;
String com2=null;
if(len%2==0){
com1=x.substring(0,len/2);
com2=x.substring(len/2,len);
}else{
com1=x.substring(0,len/2);
com2=x.substring((len/2)+1,len);
StringBuilder sb = new StringBuilder(com2);
String com3=sb.reverse().toString();
if(com1.equals(com3)){
return “YES\n”;

  }
   }
   if(com1.contentEquals(com2))
       return "YES\n";
     else
       return "NO\n";
} 

}

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

1 Like