11888 - Abnormal 89's

[bm_anas]

Any idea how to solve this problem??
Thanks in advance.

[Angeh]

FOR k : 1...n
make 2 strings 1..k and k+1... n ... now a simple check ...

[sohel]

I haven't solved this problem yet, but isn't your approach n^2 and won't it get TLE?

[Angeh]

I got AC in 0.088 with this Trivail solution ...
But i think there is also another solution ..
if the string is s ... and its reverse is r....
try to find r in s+s ..... if you use strstr() maybe you will Timeout ... )

[Leonid]

I got AC in 0.088 with this Trivail solution ...
But i think there is also another solution ..
if the string is s ... and its reverse is r....
try to find r in s+s ..... if you use strstr() maybe you will Timeout ... )

I was about to implement O(N) solution. With proper tests your solution would definitely TLE.

[Mizanur Rahman(IUK)]

TLE.... Please Help me

Code: Select all

#include<stdio.h>
#include<string.h>

int pal(char a[])
{
	char b[200000]={' '};
	//strcpy(b,a);
	long int n=strlen(a),i;
	//strrev(b);
	for(i=0;i<n;i++)
		b[i]=a[n-i-1];
	if(strcmp(a,b)==0)
		return 1;
	return 0;
}
int al(char a[])
{
	 long int n=strlen(a);
	  long int i,k;
	  for(i=0;i<n-1;i++)
	  {
		  long int j;k=0;
		  char b[200000]={' '},c[200000]={' '};
		  strncpy(b,a,i+1);
		   if(pal(b))
		  {
		  for(j=i+1;j<n;j++)
		  {c[k]=a[j];k++;}
			  if(pal(c)) return 1;
		  }
	  }
	  return 0;
}
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
	char a[200000];
	scanf("%s",a);
	if(al(a))
		printf("alindrome\n");
	else if(pal(a))
		printf("palindrome\n");
	else printf("simple\n");
	}
	return 0;
}

[Leonid]

Mizanur, on each iteration when looking for alindrome the algorithm copies whole string. Try to find a way not to copy the string and I believe it should be AC.

[patsp]

How to solve this problem in O(N) ??

[Angeh]

if the string is s ... and its reverse is r....
try to find r in s+s

[robot]

Hi anas
if You solve this problem O(n) , you have to try using KMP(only just Prefix function)

ASU(SUST)

[Repon kumar Roy]

I am using HASHING TO find if S[L.. R] is a palindrome or not ?
But getting TLE .. Please Help ?

Code: Select all

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				200005
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define msg(x)			cout<<x<<endl;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ull ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

char P[LMT] , RP[LMT];
ull H [LMT];
ull RH[LMT];
ull base = 117;
const ull MOD =1000000007ULL;
ull kPower[LMT];

ull getHash (int L,int R,ull HASH[])
{
	ull kp =( MOD +  HASH[R] - (L>0 ? HASH[L-1] : 0)) % MOD ;
	kp =( kp * modinverse(kPower[L], MOD)) % MOD;
	return kp;
}
int main()
{
	
	
	int tc ;
	scanf("%d",&tc);
	ull t = 1;
	for(int i = 0 ; i < LMT ; i ++ ) {
		kPower[i] = t % MOD;
		t = (t * base ) % MOD ;
	}
	while (tc -- ) {
		scanf("%s", P );
		int len = (int) strlen(P);
		strcpy(RP , P);
		reverse(RP, RP + len);
		
		ull hash = 0 ;
		for (int i = 0 ; i < len ; i ++ ) {
			H[i] = hash + kPower[i]*( P[i] -'a' +1 );
			H[i] %= MOD;
			hash = H[i];
		}
		hash = 0;
		for (int i = 0 ; i < len ; i ++ ) {
			RH[i] = hash + kPower[i]*( RP[i] -'a' + 1);
			RH[i] %= MOD;
			hash = RH[i];
		}
		
		int isp = 0;
		if(RH[len-1] == H[len-1]) isp = 1;
		
		for (int k = 0 ; k < len - 1  ; k ++ ) {
			ull fh = getHash(0,k,H);
			ull rfh = getHash(len - 1 - k , len-1 , RH );
			
			ull lf = getHash(k+1, len-1 , H);
			ull rlf = getHash(0, len - 1 - k - 1, RH );
			if (fh == rfh && lf == rlf ) {
				isp =2;
				break;
			}
		}
		
		if(isp >= 2) printf("alindrome\n");
		else if (isp == 1 ) printf("palindrome\n");
		else printf("simple\n");
		
		
	}
	return 0;
}

[Mukit Chowdhury]

A little bit confused !!! Though I've got AC, but I'm not sure, if my solution should get this verdict.

I have tried with each index so that by this index, I can make two palindrome from 0 to index and index+1 to len-1. If I can make two palindrome, then given input is alindrome, otherwise not. If the input string length is 200000 and first half of that string is a palindrome and second half of that string is not a palindrome, then my case should get TLE. Shouldn't that?

Would anyone please give me the answer?