11888 - Abnormal 89's

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
bm_anas
New poster
Posts: 10
Joined: Fri May 15, 2009 9:13 pm

11888 - Abnormal 89's

Post by bm_anas » Sun Oct 31, 2010 3:21 am

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

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11888 - Abnormal 89's

Post by Angeh » Sun Oct 31, 2010 10:03 am

FOR k : 1...n
make 2 strings 1..k and k+1... n ... now a simple check ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11888 - Abnormal 89's

Post by sohel » Sun Oct 31, 2010 10:13 am

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

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11888 - Abnormal 89's

Post by Angeh » Sun Oct 31, 2010 10:39 am

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 ... :))
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11888 - Abnormal 89's

Post by Leonid » Sun Oct 31, 2010 11:32 pm

Angeh wrote: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)
New poster
Posts: 12
Joined: Wed Aug 18, 2010 12:07 pm

Re: 11888 - Abnormal 89's

Post by Mizanur Rahman(IUK) » Mon Nov 01, 2010 3:33 pm

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11888 - Abnormal 89's

Post by Leonid » Mon Nov 01, 2010 3:42 pm

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
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11888 - Abnormal 89's

Post by patsp » Mon Nov 01, 2010 6:14 pm

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

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11888 - Abnormal 89's

Post by Angeh » Mon Nov 01, 2010 6:15 pm

if the string is s ... and its reverse is r....
try to find r in s+s
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: 11888 - Abnormal 89's

Post by robot » Tue Apr 26, 2011 9:00 pm

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

ASU(SUST) :)

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11888 - Abnormal 89's

Post by Repon kumar Roy » Wed Apr 29, 2015 5:32 pm

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
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11888 - Abnormal 89's

Post by Mukit Chowdhury » Mon Nov 30, 2015 2:35 pm

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?

Post Reply

Return to “Volume 118 (11800-11899)”