Codeforces Global Round 7

help
1

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.

2

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)

AC on your code!

3 Likes
3

Same issue I also had :

4

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

5

Finally got the AC

6

May you provide link of your code?
and what algorithm did you use?

7

thank you @fog856

8

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