CHFDORA Video Solution

Here it is: https://youtu.be/FISSy6jKx0Q
Commented code:
https://www.codechef.com/viewsolution/28942268 O((nm)^1.5)
https://www.codechef.com/viewsolution/28942025 O(nm)
To solve in O(nm):
https://www.hackerrank.com/topics/manachers-algorithm
https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/
Comments, questions, requests, criticism, are all welcome!

2 Likes

Hey! In my code only 1 test case gives TLE… plz help which edge case i am missing

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

You should loop for length inside of the loop for i, j and break when SIc >= 0 && EIc <m && SIr >= 0 && EIr <n

for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
int SIc = j-(length/2);
int EIc = j+(length/2);
int SIr = i-(length/2);
int EIr = i+(length/2);

	                if (SIc >= 0 && EIc <m && SIr >= 0 && EIr <n){
	                    boolean a = checkpallindromec(arr,SIc,EIc,i);
	                    if (a == true){
	                    boolean b = checkpallindromer(arr,SIr, EIr,j);
	                   
	                    if (a == true && b== true) pairs++;
	                   
	                    }
	                }
	                
	            }
	        }
	        
	        length +=2;

here, it would enter if statement only when the conditions u mentioned are true,… why and where to add a break statement…
i am not getting u …

Actually, never mind what I said about the loops. Simply set endp in your code to Math.min(n, m).

whats endp !?

The variable endp in your code.

1 Like

it did give correct ans… thankss
But what was wrong … as in why was that 1 test case was giving TLE !?
And also, how did u come up with this error …

You need min(n, m) instead of m to guarantee that the time complexity of the solution is good

Ohkk… Got it now… Thanks

No problem

https://www.codechef.com/viewsolution/28879137
why im i getting TLE for last 2 test cases…plzz help

Unfortunately, Python is slow for big inputs…
Most submissions which obtain 100 (https://www.codechef.com/status/CHFDORA?sort_by=All&sorting_order=asc&language=116&status=15&handle=&Submit=GO) run close to the time limit.

thanks bro …my bad

No problem. The good thing about long challenges is that you have a lot of time to rewrite solutions in another language if you need to.

1 Like

Submit using PYPY3 it will work.

1 Like