@anupam_datta Instead of re-declaring or clearing the vector try to overwrite it.
Re-declaring or clearing a vector has time complexity of O(n) where n is the size of vector.
I have passed string as reference in my palindrome function so it should not copy the whole string.
https://www.codechef.com/viewsolution/9269046
Why still getting TLE in subtask 3?
My (simplified) understanding of the solution:
Iterate over all possible values of the Order p (starting from 2) and treat every index i as centre of the palindromic subsequence. Treating i as the centre allows us to check if the subsequence is a palindrome on the fly, because we only have to check the newly added peripheral characters on the left and the right. We are assured that the subsequence we have till now is a palindrome already, so we only have to check if the newly added characters on the left and right of the subsequence match each other or not. Be careful to consider 2 cases here:
First Case (Your palindrome is an odd length palindrome):
The character at index i can be the centre of a palindrome so in this case you have to check the characters to the left and right(not immediate left and right) of i. Call them start and finish. Initially, start will be equal to i/p and finish will be equal to i X p… if start and finish are equal, then great, increment your answer by 1 and set start = start/p and finish = finish X p. Obviously if start and finish violate any boundary conditions like start%p !=0 OR finish > length of string OR obviously if character at start != character at finish, then you should break from this inner loop and start considering the next index i+1 as the centre of your palindromic subsequence.
Second Case (Palindrome is of even length:) Treat the index i as one of the 2 characters which form the centre of your even length palindrome. In this case the start will be equal to i (instead of i/p) and finish will be the same as previous case: i*p. Perform the same checks as before, checking everytime if start==finish and if yes, set start = start/p and finish = finish/p. Break if start%p != 0 OR if finish is greater than the length of the string OR if start != finish.
Caveat: As mentioned in the editorial, you will have to add the length of the string to your answer because every subsequence of length is a valid answer. This hack allows us to start considering subsequences whose length is at least 2, otherwise, as mentioned, we will end up with an O(n^2) algorithm, which will fail horribly.
Please see the linked tester’s excellent solution for the implementation details.
I am not sure but I think your code’s complexity is somewhat O(N2log(N)) which isn’t enough for subtask 3.
1 Like
It’s an idea for speeding it up, but won’t solve his TLE.
You almost manage to solve it, but you did one very inefficient thing. Notice that you are passing a string by a value to your palindrome checking function. This causes copying the whole string during each call to this function. I change the function to operate on a global variable and the solution passed: CodeChef: Practical coding for everyone
2 Likes
This is my solution which got tle CodeChef: Practical coding for everyone
This is which get accepted
https://www.codechef.com/viewsolution/9268112
I get your point, but look at my comment to his question. His main issue is passing the string by a value to the palindrome checking function.
oh! sorry, I misunderstood that.you are right.
Double check for possible overflows.
Wouldn’t overflow produce a WA rather than a runtime error ?
1 Like
It depends on the execution. For example, you may try to access some unbounded entries of an array etc. I submitted your solution using long long type where appropriate and it passed: CodeChef: Practical coding for everyone
My bad, I might have been accessing negative index entries in the array due to overflow.
1 Like
thanks!!!
This line is not very efficient: temp = temp+S[cnt];
1 Like
Thanks buddy. Understood my mistake.
+= operator is much more efficient than + operator in case of concatenation (now no new copy of string is created).