# Codeforces Global Round 7

This is the code Code Submitted I submitted for problem D2problem . I am getting TLE, may anyone help me?
I used manacher’s algorithm to solve this problem.

It’s because you declared MAX to be < 10^6 (the maximum limit).
it’s a deceptive TLE, it’s a memory issue. (I don’t know the specifics, perhaps someone who understands the C++ language better will know, I only assume the rational explanation that it tries to allocate more memory dynamically which results in the excess amount of time taken)

3 Likes

Same issue I also had :

HI there. I am having the same problem. my solution is O(N) but it is still giving a TLE

Finally got the AC

and what algorithm did you use?

thank you @fog856

I have used Manacher’s algorithm to find the longest palindromic substring. Now I have modified it a little to get the longest palindromic substring which either starts on the first character or ends on the last character.

This is my code:

``````/*Priyansh Agarwal*/
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
void manacher_algo(string s,int n)
{
int *arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=0;
int center_of_longest=0;
int right_limit=0;
for(int i=1;i<n-1;i++)
{
int mirror=2*center_of_longest-i;
if(i<right_limit)
arr[i]=min(right_limit - i,arr[mirror]);
while(s[i+(1+arr[i])]==s[i-(1+arr[i])])
arr[i]++;
if(i+arr[i]>right_limit)
{
center_of_longest=i;
right_limit=i+arr[i];
}
}
int max_length=0;
int index=-1;
for(int i=1;i<n-1;i++)
{
if(arr[i]>max_length && i-arr[i]==1)
{
index=i;
max_length=arr[i];
}
if(arr[i]>max_length && arr[i]+i==n-2 )
{
index=i;
max_length=arr[i];
}
}
int left=index-max_length;
int right=index+max_length;
for(int i=left;i<right;i++)
if(s[i]!='#')
cout<<s[i];
delete[] arr;
}
string prime_string(string s,int n)
{
string s2="\$#";
for(int i=0;i<n;i++)
{
s2+=s[i];
s2+='#';
}
s2+='@';
return s2;
}
int main()
{
fastio();
#ifndef ONLINE_JUDGE
freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
#endif
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n=s.length();
int counter=0;
string ans="";
for(int i=0;i<n/2;i++)
{
if(s[i]==s[n-1-i])
{
ans+=s[i];
counter++;
}
else
break;
}
if(counter==n/2)
cout<<s<<endl;
else
{
string s2=s.substr(counter,n-2*counter);
int len=n-2*counter;
string s3=prime_string(s2,len);
cout<<ans;
manacher_algo(s3,s3.length());
reverse(ans.begin(),ans.end());
cout<<ans<<endl;
}
}
return 0;
}``````
1 Like