LAPIN - Editorial

thewarhero_78 · October 31, 2019, 7:12am

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

}

ssjgz · October 31, 2019, 8:42am

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

thewarhero_78 · October 31, 2019, 9:09am

Thank you for replying !! Here is the link to my submission:-CodeChef: Practical coding for everyone

ssjgz · October 31, 2019, 9:13am

Thanks - your submission fails for the following testcase:

1
abba

thewarhero_78 · October 31, 2019, 9:17am

How did you check this?
i mean how did you know the reason for rejection of my submission!!

ssjgz · October 31, 2019, 9:19am

I usually write a testcase generator for the problems I solve - I droned on about the process here. It was then a simple matter to check the output from your program against known-correct answers to random testcases until one failed

Edit:

To be clear - I don’t know if Codechef run that particular abba testcase, but it’s definitely a testcase that exposes a flaw in your program

thewarhero_78 · October 31, 2019, 9:29am

Okay thank you my friend for helping me out and teaching me new stuff. I have successfully removed that flaw from my code and tried to resubmit but still my submission gets rejected and its very frustrating. Here is the link of my new submission CodeChef: Practical coding for everyone
Please have a look in it.

ssjgz · October 31, 2019, 10:05am

This fails on

1
abbbabbab

I suggest re-reading the Problem very carefully, as your current approach isn’t going to work

thewarhero_78 · October 31, 2019, 10:47am

Okay thank you for helping me !!

klakho · December 17, 2019, 4:58pm

thanks once again ssjgz can u tell me how to generate testcases

ssjgz · December 17, 2019, 5:03pm

Here’s lapindrome complete with testcase generator:

// Simon St James (ssjgz) - 2019-10-29
// 
// Solution to: https://www.codechef.com/problems/LAPIN
//
#include <iostream>
#include <array>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

constexpr auto numLetters = 26;

array<int, numLetters> letterHistogram(const string& s)
{
    array<int, numLetters> letterHistogram = {};
    for (const auto letter : s)
    {
        letterHistogram[letter - 'a']++;
    }
    return letterHistogram;
}

bool isLapindrome(const string& s)
{
    const int length = s.length();
    const auto leftHalf = s.substr(0, length / 2);
    const auto rightHalf = s.substr(length - length / 2);

    return letterHistogram(leftHalf) == letterHistogram(rightHalf);
}

#if 0
SolutionType solveOptimised()
{
    SolutionType result;
    
    return result;
}
#endif


int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    if (argc == 2 && string(argv[1]) == "--test")
    {
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
        //const int T = rand() % 100 + 1;
        const int T = 1;
        cout << T << endl;

        for (int t = 0; t < T; t++)
        {
            const int len = 1 + rand() % 12;
            const int maxChar = 1 + rand() % numLetters;

            string s;
            for (int i = 0; i < len; i++)
            {
                s.push_back('a' + rand() % maxChar);
            }
            cout << s << endl;
        }

        return 0;
    }
    
    const auto T = read<int>();

    for (int t = 0; t < T; t++)
    {

        const auto s = read<string>();
        cout << (isLapindrome(s) ? "YES" : "NO") << endl;
    }

    assert(cin);
}

To generate a testcase, just run the executable and pass it the --test flag on the command-line e.g if the executable is called a.out:

./a.out --test

See also:

aditya_oke · January 7, 2020, 6:06am

The implementation of the logic as given in Editorial in Python3

t = int(input())
while(t>0):
    d =  {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
    s = input()
    ln = len(s)
    fg = 0
    s1 = ""
    s2 = ""
    if(ln % 2 == 0):
        s1 = s[:ln//2]
        s2 = s[ln//2:]
        # print(s1, s2)
    else:
        s1 = s[:ln//2]
        s2 = s[(ln//2)+1:]
        # print(s1, s2)
    
    for i in s1:
        d[i] += 1
    
    for j in s2:
        d[j] -= 1
        
    # print(d)
    
    for i in d.values():
        if(i != 0):
            fg = 1
            break
    if(fg == 1):
        print("NO")
    else:
        print("YES")
    t -= 1

amandeep17 · March 10, 2020, 3:27pm

Can somebody help me out whats wrong in my code?
https://www.codechef.com/viewsolution/30273757

ssjgz · March 10, 2020, 4:03pm

Consider the testcase:

5
bbcccbe
gedce
eccbdde
bdfbdbe
egafded

amandeep17 · March 11, 2020, 9:50am

tnx bro…i got it…i didn’t clear the map.

ssjgz · March 11, 2020, 9:54am

Even better would be to just write your code so that this kind of problem simply can’t happen in the first place; none of l,l1,i,s or m are used outside of the while block, so why declare them there?

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

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int l,l1,i;
        string s;
        map<char,int> m;
        cin>>s;
        l=s.size()/2;
        if(l==0)
        {
            cout<<"NO\n";
            continue;
        }
        if(s.size()%2==0)
        {

            l1=l;
        }
        else
        {
            l1=l+1;
        }
        i=l1;
        while(i<s.size())
        {
            if(m.find(s[i])==m.end())
            {
                m.insert(pair<char,int>(s[i],1));
            }
            else
                m[s[i]]++;
            i++;
        }
        for(i=0;i<l;i++)
        {
            if(m.find(s[i])==m.end()|| m[s[i]]==0)
            {
                cout<<"NO\n";
                break;
            }
            else
                m[s[i]]--;
        }
        if(i==l)
        {
            cout<<"YES\n";
        }
    }
    return 0;
}

or better still:

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

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        const int l=s.size()/2;
        if(l==0)
        {
            cout<<"NO\n";
            continue;
        }
        int l1 = l;
        if(s.size()%2!=0)
        {
            l1=l + 1;
        }
        int i=l1;
        map<char,int> m;
        while(i<s.size())
        {
            if(m.find(s[i])==m.end())
            {
                m.insert(pair<char,int>(s[i],1));
            }
            else
                m[s[i]]++;
            i++;
        }
        for(i=0;i<l;i++)
        {
            if(m.find(s[i])==m.end()|| m[s[i]]==0)
            {
                cout<<"NO\n";
                break;
            }
            else
                m[s[i]]--;
        }
        if(i==l)
        {
            cout<<"YES\n";
        }
    }
    return 0;
}

amandeep17 · March 12, 2020, 5:34am

but there may be repeated memory allocation and memory release for them… will it affect performance of code?

ssjgz · March 12, 2020, 6:50am

The construction of an empty string or an empty map should not involve memory allocations.

amandeep17 · March 12, 2020, 6:51am

got it …Thank you sir…

codex_gigas · March 18, 2020, 2:08pm

whats wrong in this solution

include<bits/stdc++.h>

using namespace std;

int main()
{
int i,j,count=0;
int t;
cin>>t;
while(t–)
{ int n;
string s;
cin>>s;
n=s.length();
if(n%2==0)
{
for(i=0;i<n/2;i++)
{
for(j=n/2;j<n;j++)
{
if(s[i]==s[j])
{
count++;
}
}

						}
						if(count==n/2)
						cout<<"yes"<<endl;
						else
						cout<<"no"<<endl;
				}
				else if(n%2!=0)
					{
						for(i=0;i<n/2;i++)
						{
							for(j=(n+1)/2;j<n;j++)
								{
									if(s[i]==s[j])
									{
										count++;
									}
								}
								
						}
						if(count==n/2)
						cout<<"yes"<<endl;
						else
						cout<<"no"<<endl;
					
					
				}
		}
		return 0;
}