LAPIN - Editorial

editorial
, , , ,
21

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.

22

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!

CodeChef: Practical coding for everyone 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!!!

23

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

4 Likes
24

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

25

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
26

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

27

Here is your AC code with array size increased. CodeChef: Practical coding for everyone

3 Likes
28

try this:
1
abac

29

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

30

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

31

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

32

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

33

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

34

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

35

why is this wrong

37 
    #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;
}
38

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

}

40

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

41

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";
}

}

42

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