719 - Glass Beads

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

Moderator: Board moderators

DJYA
New poster
Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm

Post by DJYA » Wed Feb 18, 2004 9:16 am

Adrian Kuegel wrote:It is possible to solve this problem in O(n).
Could anyone please give me more hint ?
I don't know how to do it in O(n)

javier lira
New poster
Posts: 1
Joined: Sun Mar 07, 2004 3:30 pm

719 -- Glass Beads

Post by javier lira » Mon Mar 08, 2004 7:08 pm

TLE in C++, i don't have more ideas :cry: , someone to help me or give me a hint, please!!!!!!

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Thu May 20, 2004 12:07 am

Any more hint on the linear approach?

hackfox
New poster
Posts: 8
Joined: Fri Aug 08, 2003 9:39 pm

Try a sequence of 10000 'a'

Post by hackfox » Mon Jun 28, 2004 10:18 pm

Hi javier lira,

You can try a case with aaaaa.....(repeat 10000 times)
or try a case with aaaaa...(5000 times)...bbbbb...(5000 times).

Remember that you don't need to scan from left to right for the start point with step 1 always.

If there are matches more than one characters, you can move to next start point with more steps.

--
The keypoint is that there is one string only :)

rskvijay
New poster
Posts: 3
Joined: Fri Mar 23, 2007 5:57 pm

Post by rskvijay » Thu Sep 06, 2007 5:43 pm

hav submitted this many times and i keep on getting wrong answer..
my program runs in O(n) time.. can i have some test cases plzzz??

thanx,
vijay.

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

Post by 20717TZ » Wed Feb 13, 2008 7:35 am

Hi javier lira,

You can try a case with aaaaa.....(repeat 10000 times)
or try a case with aaaaa...(5000 times)...bbbbb...(5000 times).

Remember that you don't need to scan from left to right for the start point with step 1 always.

If there are matches more than one characters, you can move to next start point with more steps.
What do you mean "If there are matches more than one characters"? I cannot understand. Would mind give me a clear explanation, and give me the examples? Thanks.

I do have the case "aaaa...."(10000), and "aaaa....bbbb" as you mentioned. They are running slow because of my algorithm is O(n*n).

Thanks.
I Believe I Can - leestime.com

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

Re: 719 - Glass Beads

Post by Angeh » Thu Aug 19, 2010 3:47 pm

I Need some Clear hints please .....
how to find the O(n) algorithm ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 719 - Glass Beads

Post by suneast » Fri Dec 31, 2010 7:32 am

hi , all :
I think I have a better O(N) solution using an Algorithm by "??(ZhouYuan)" called "?????(Minimum Expression)" in Chinese.. :wink:

Code: Select all

@ double the string -> str[] = "String""String"
@ i=0 j=1 k=0 len=str.length()
   while(i<len && j<len)
      # if(str[i+k] == str[j+k]) { k++; if(k==len) break; }
      # if(str[i+k] > str[j+k])  { i=i+k+1;  if(i<=j) i=j+1; k=0; }
      # if(str[i+k] < str[j+k])  { j=j+k+1; if(j<=i) j=i+1; k=0; }

   return Min(i,j)
A simple code using O(N)time above will solve the problem :wink:

if U want to know more details about the algorithm, you can search the Internet using keyword "?? ?????" (in Chinese)

Hope I'm help to you all :D

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 719 - Glass Beads

Post by zobayer » Wed Feb 16, 2011 9:51 am

I am getting wrong answer. I used suffix array to solve the problem. This is my algorithm: I concatenate the string with the original one and then construct the sorted suffix array. The first suffix starting in the first string is the answer. Is there anything wrong with this approach? Can there be words of 0 length?
Thanks in advance...
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 719 - Glass Beads

Post by zobayer » Wed Feb 16, 2011 10:21 am

Got AC!
The case was "aaaa", how could I miss such a trivial case :(
Input is nice. No blank line or anything.
Last edited by zobayer on Wed Feb 16, 2011 10:43 am, edited 1 time in total.
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 719 - Glass Beads

Post by zobayer » Wed Feb 16, 2011 10:26 am

suneast wrote:hi , all :
I think I have a better O(N) solution using an Algorithm by "??(ZhouYuan)" called "?????(Minimum Expression)" in Chinese.. :wink:

A simple code using O(N)time above will solve the problem :wink:

if U want to know more details about the algorithm, you can search the Internet using keyword "?? ?????" (in Chinese)

Hope I'm help to you all :D
Damn this is cool, I got AC with both Suffix Array and yours algorithm. My suffix array implementation was also O(n). But considering the coding complexity, suffix array is a shit when compared to this... Thanks for sharing!
You should not always say what you know, but you should always know what you say.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 719 - Glass Beads

Post by DD » Sat Mar 19, 2011 11:07 pm

I am curios how to use suffix array to solve this problem since it also needs sorting which needs O(nlogn) time. I solved this problem by the aforementioned minimum expression. That algorithms is really cool :D , looks like a twist of Boyer-Moore string matching algorithm.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 719 - Glass Beads

Post by Shafaet_du » Fri Oct 14, 2011 11:38 pm

With same code i got ac in spoj,live archive but getting TLE in uva. why??

quietroit
New poster
Posts: 2
Joined: Wed Nov 02, 2011 9:06 pm

Re: 719 - Glass Beads

Post by quietroit » Thu Nov 10, 2011 11:56 am

What code do you use? By suneast?

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

Re: 719 - Glass Beads

Post by Repon kumar Roy » Wed May 06, 2015 9:15 am

WHY RTE ??
COULD not FIND ANY ERROR...

Code: Select all


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

/*------- Constants---- */
#define LMT				400006
#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;
#define EPS				1e-7
/*---- 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){
	ll 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 ****************************/


#define LG 21
char A[LMT];
struct entry {
	int nr[2], p;
} L[LMT] , T[ LMT ];
int P[LG][LMT], N, i, stp, cnt;
int counterAray[LMT];
int prefixArray[LMT];

int cmp(struct entry a, struct entry b)
{
	return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
	
}

void countingSort (entry v[] , int index , int len )
{
	int iM = -100;
	for(int  i = 0 ; i < len ; i ++ ){
		iM = max(iM , v[i].nr[index] + 1);
	}
	
	
	memset(counterAray ,0, (iM + 1) * sizeof(int));
	for(int i = 0 ; i< len; i ++ ) {
		counterAray[v[i].nr[index] + 1] ++;
	}
	
	prefixArray[0] = counterAray[0];
	for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
		prefixArray[i] = counterAray[i] + prefixArray[i-1];
	}
	
	for (int i = len - 1; i >=0 ; i -- ) {
		prefixArray[v[i].nr[index] + 1] --;
		
		if( prefixArray[v[i].nr[index] + 1] < 0 ) {
			printf("ARRAY LESS\n");
		}
		T[prefixArray[v[i].nr[index] + 1]] = v[i];
	}
	
	for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
	
}
void buildSA()
{
	
	for (N = strlen(A), i = 0; i < N; i ++)
		P[0][i] = A[i] - 'a';
	for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
	{
		for (i = 0; i < N; i ++)
		{
			L[i].nr[0] = P[stp - 1][i];
			L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
			L[i].p = i;
		}
		//countingSort(L , 1 , N);
		//countingSort(L , 0 , N );
		
		sort(L, L + N , cmp);
		for (i = 0; i < N; i ++)
			P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
		
		
	}
}

int lcp(int x, int y)
{
	int k, ret = 0;
	if (x == y) return N - x;
	for (k = stp - 1; k >= 0 && x < N && y < N; k --){
		
		if( k >= LG ) {
			printf("LHSLHDD\n");
		}
		if (P[k][x] == P[k][y])
			x += 1 << k, y += 1 << k, ret += 1 << k;
	}
	return ret;
	
}

int main()
{
	int tc;
	
	//freopen("in.txt", "r", stdin);
	sc(tc);
	
	while (tc -- ) {
		scanf("%s",A);
		strcat(A, A );
		
		buildSA();
		int ans = -1;
		for(int i = 0; i < N -1  ; i ++ ) {
			if(L[i].p < N/2 ) {
				if(ans ==-1 ) ans = L[i].p;
				
				if(lcp( ans ,  L[i + 1].p ) >= N / 2 ) {
					if( ans > L[i+1]. p ) ans = L[i+1].p;
				}
			}
		}
		
		printf("%d\n", ans + 1 );
	}
}


Post Reply

Return to “Volume 7 (700-799)”