Stuck with a problem

help
,
1

i am stuck with a problem link - PRPALN Problem - CodeChef . I have solved it partially . i have read other’s solution . i found another participant’s solution who got all test cases passed .his code is similar to mine , i cant figure out why i am not getting all test cases passed. i have checked both code around 10 times.
please help me out .

my code - CodeChef: Practical coding for everyone
other participants code - CodeChef: Practical coding for everyone

2

Testcase:

3
 caccac
acaccac
 caccaca

Your Output:

YES
NO
YES

Expected Output:

YES
YES
YES

Notice how caccac is an palindrome. But depending on which side you add another a, your code will either work or fail.

The reason your code fails: 
if (s[j - 1] == s[i]) {
   j -= 2;
   ;
   i++;
   used = 1;
} else if (s[i + 1] == s[j]) {
   i += 2;
   j--;
   used = 1;
}

^this logic is not working properly. You have 2 cases, one where you have to remove the character at index i, another where you have to remove at the index j. The way you decide which one to delete is faulty. Note: you try to do it in O(1), which is not possible. The fastest approach would be in O(n)
in the Testcase I gave you above, you need to delete at index j, but you delete at index i.

one way to fix

I would replace your if statement with this:

if(s[i] != s[j])
   if(string_after_i_removed_is_palindrome) print YES
   else if(string_after_j_removed_is_palindrome) print YES
   else print NO
   return

Basically, you tried to decide whether to delete the character at index i or j.
But you should simply test both cases, without thinking. Just bruteforce it. Your code will still run in O(n), so there is no problem.

1 Like
3

thanks @termii

if it’s not too much to ask can you please tell how did you came with this unique testcase ? reason , I am asking is because I want to know how to come up with test cases where one’s code could fails ?

4

you are mistaken. I did not find your error by guessing testcases.

What exactly threw me off? In your code, you find the i- and j-position where the palindrome breaks, meaning you find the positions where you have to remove a character. But the way to determine which one to remove looked faulty. Because you assume that s[j-1]==s[i] implies s[i+1]!=s[j].
I did not know this assumption was verified, so on my way to verify it, I found the error.

To sum it up, I found your error, because I have experience with these kinds of problems. If you keep solving problems like that, you will understand the underlying language more and more.

5

thank you @termii for helping me out .

6

hii @termii , can you please tell me what’s wrong with my code , as it is getting “WA” on last test case?
question: XORAND Problem - CodeChef
my code: CodeChef: Practical coding for everyone