Posted:

**Fri Oct 26, 2001 7:40 pm**Who have either its solution or algorithm please tell me. Thank you.

Page **1** of **2**

Posted: **Fri Oct 26, 2001 7:40 pm**

Who have either its solution or algorithm please tell me. Thank you.

Posted: **Sat Oct 27, 2001 12:30 am**

Just generate all the first n sequences using backtracking, and print the last one.

Kristoffer Hansen

Kristoffer Hansen

Posted: **Sat Oct 27, 2001 6:29 am**

Oh really ? If we do that, n must be very small ! The problem didn't tell anything about the limit of n. I only want to ask that : did u get accepted ?

Posted: **Sat Oct 27, 2001 12:32 pm**

Ofcourse I did get accepted, check it out for yourself:

123 | 0:00.000 | 64 | Kristoffer Hansen |

C | Iterative enumeration | 2001/05/08-21:41:21.029

123 | 0:00.000 | 64 | Kristoffer Hansen |

C | Iterative enumeration | 2001/05/08-21:41:21.029

Posted: **Mon Oct 29, 2001 6:59 am**

Only 501? That is amazing. Thank you for your suggestions.

Posted: **Fri Sep 05, 2003 11:42 am**

Quick question... For problem #129, it says that, for the sample input of

30 3 the output is

ABAC ABCA CBAB CABA CABC ACBA CABA

28

Why isn't it

ABAC ABCA CBAB CABA CABC ACBA CABA CB

30

For this problem, I know how to build an infinitely long square-free string, but I don't know how to output it correctly.

Thanks to everyone!

30 3 the output is

ABAC ABCA CBAB CABA CABC ACBA CABA

28

Why isn't it

ABAC ABCA CBAB CABA CABC ACBA CABA CB

30

For this problem, I know how to build an infinitely long square-free string, but I don't know how to output it correctly.

Thanks to everyone!

Posted: **Fri Sep 05, 2003 1:30 pm**

String should be smallest ....

Best regards

DM

Best regards

DM

Posted: **Fri Sep 05, 2003 1:54 pm**

Sorry.. My bad.. I forgot to take into account the strings which are the same length, but at different levels.

For example, the first 30 levels will be:

Which actually produces 28 characters. My initial assumption was that each level has to have that many characters.

Funny, when I did a search on the board for this problem, I found nothing. So it must be incredibly easy, huh?

One more question: can this be done somehow by using the Zimin series? The method I used was backtracking, kinda like Dijkstra did for the same type of problem, but it has an exponential running time.

Later!

For example, the first 30 levels will be:

Code: Select all

```
A
AB
ABA
ABAC
ABACA
ABACAB
ABACABA
ABACABC
ABACABCA
ABACABCAC
ABACABCACB
ABACABCACBA
ABACABCACBAB
ABACABCACBABC
ABACABCACBABCA
ABACABCACBABCAB
ABACABCACBABCABA
ABACABCACBABCABAC
ABACABCACBABCABACA
ABACABCACBABCABACAB
ABACABCACBABCABACABC
ABACABCACBABCABACABCA
ABACABCACBABCABACABCAC
ABACABCACBABCABACABCACB
ABACABCACBABCABACABCACBA
ABACABCACBABCABACABCACBAB
ABACABCACBABCABACABCACBAC
ABACABCACBABCABACABCACBACA
ABACABCACBABCABACABCACBACAB
ABACABCACBABCABACABCACBACABA
```

Funny, when I did a search on the board for this problem, I found nothing. So it must be incredibly easy, huh?

One more question: can this be done somehow by using the Zimin series? The method I used was backtracking, kinda like Dijkstra did for the same type of problem, but it has an exponential running time.

Later!

Posted: **Tue Sep 09, 2003 10:57 pm**

xbeanx wrote:

"For this problem, I know how to build an infinitely long square-free string, but I don't know how to output it correctly."

really? i'm very much curious about it. would you care to explain me how you can produce such an infinite sequence?

also, i solved this problem with a recursive function. the basic idea is that all subsequences of a legal sequence are also legal sequences. this may seem obvious, but it allows one to solve it with near linear complexity.

best regards.

"For this problem, I know how to build an infinitely long square-free string, but I don't know how to output it correctly."

really? i'm very much curious about it. would you care to explain me how you can produce such an infinite sequence?

also, i solved this problem with a recursive function. the basic idea is that all subsequences of a legal sequence are also legal sequences. this may seem obvious, but it allows one to solve it with near linear complexity.

best regards.

Posted: **Sat Oct 16, 2004 2:43 pm**

I'm tired to say that why I always get WA on this problem.

my C++ code:

/////////////////////////////////////////////////////////////////////////////////////

#include <iostream.h>

int n;

int L;

int* Sequence;

int num;

int last;

int isHard(int t, int range)

{

int cls;

int i, j;

int mark;

cls = (range+1)/2;

for (i=2; i<=cls; i++)

{

mark=0;

for (j=0; j<i; j++)

{

if ((range-j>=0)&&(range-j-i>=0))

{

if (Sequence[range-j]==Sequence[range-j-i])

{

mark++;

}

else

{

break;

}

}

else

{

break;

}

}

if (mark==i)

return 0;

}

return 1;

}

int backdating(int index)

{

if (num>=n)

{

last = index-1;

return 1;

}

for (int i=0; i<L; i++)

{

if (Sequence[index-2]==i)

continue;

Sequence[index-1] = i;

if (isHard(i, index-1)>0)

{

num++;

if (backdating(index+1)>0)

return 1;

}

}

return 0;

}

int main()

{

int i, j, k;

char c;

while (1)

{

cin>>n>>L;

if ((n==0)&&(L==0))

break;

if (cin.eof())

break;

if ((n<0)||(L>26)||(L<1))

return 1;

Sequence = new int[n];

for (i=0; i<n; i++)

{

Sequence* = 0;*

}

num = 1;

last = 1;

backdating(2);

j = 0;

k = 0;

for (i=0; i<last; i++)

{

c = 'A'+Sequence*;*

cout<<c;

j++;

if (j==4)

{

if (k==15)

{

if (i!=last-1)

{

cout<<endl;

j = 0;

k = 0;

}

}

else

{

if (i!=last-1)

{

cout<<" ";

j = 0;

k++;

}

}

}

}

cout<<endl;

cout<<last<<endl;

}

return 0;

}

////////////////////////////////////////////////////////////////////////////////////

i don't understand ...is it wrong answer?

help me !!!!

my C++ code:

/////////////////////////////////////////////////////////////////////////////////////

#include <iostream.h>

int n;

int L;

int* Sequence;

int num;

int last;

int isHard(int t, int range)

{

int cls;

int i, j;

int mark;

cls = (range+1)/2;

for (i=2; i<=cls; i++)

{

mark=0;

for (j=0; j<i; j++)

{

if ((range-j>=0)&&(range-j-i>=0))

{

if (Sequence[range-j]==Sequence[range-j-i])

{

mark++;

}

else

{

break;

}

}

else

{

break;

}

}

if (mark==i)

return 0;

}

return 1;

}

int backdating(int index)

{

if (num>=n)

{

last = index-1;

return 1;

}

for (int i=0; i<L; i++)

{

if (Sequence[index-2]==i)

continue;

Sequence[index-1] = i;

if (isHard(i, index-1)>0)

{

num++;

if (backdating(index+1)>0)

return 1;

}

}

return 0;

}

int main()

{

int i, j, k;

char c;

while (1)

{

cin>>n>>L;

if ((n==0)&&(L==0))

break;

if (cin.eof())

break;

if ((n<0)||(L>26)||(L<1))

return 1;

Sequence = new int[n];

for (i=0; i<n; i++)

{

Sequence

}

num = 1;

last = 1;

backdating(2);

j = 0;

k = 0;

for (i=0; i<last; i++)

{

c = 'A'+Sequence

cout<<c;

j++;

if (j==4)

{

if (k==15)

{

if (i!=last-1)

{

cout<<endl;

j = 0;

k = 0;

}

}

else

{

if (i!=last-1)

{

cout<<" ";

j = 0;

k++;

}

}

}

}

cout<<endl;

cout<<last<<endl;

}

return 0;

}

////////////////////////////////////////////////////////////////////////////////////

i don't understand ...is it wrong answer?

help me !!!!

Posted: **Mon Oct 18, 2004 8:14 am**

Can anyone give me some test data?

I have spent a lot of time on this problem!

And I think it is difficult to check out the fault by me only!

I beg your helps!

plz..........

I have spent a lot of time on this problem!

And I think it is difficult to check out the fault by me only!

I beg your helps!

plz..........

Posted: **Wed Oct 20, 2004 6:57 am**

I finaly get AC !

I'm glad to find my fault suddently when I remember words for my English

exam. For my program, I can only produce the seqences that begin with 'A', for I use backdating(2), and I assume that the first of a sequence must be A, but that obvious wrong, For example, if the input is

4 2, the output must be B.

So I change my program only a little:

to change the inital value of num to 0;

to use backdating(1);

to change if (Sequence[index-2]==i) to if ((index-2>=0)&&(Sequence[index-2]==i)

The other neednot change at all!

And I get a successful AC , TimeCost 0.000s and MemorySpent low(64k).

To review the problem again,

I feel How blinkered I was!

But I'm Very Very Happy I can fit it by myself.

Thank you all the same!

I'm glad to find my fault suddently when I remember words for my English

exam. For my program, I can only produce the seqences that begin with 'A', for I use backdating(2), and I assume that the first of a sequence must be A, but that obvious wrong, For example, if the input is

4 2, the output must be B.

So I change my program only a little:

to change the inital value of num to 0;

to use backdating(1);

to change if (Sequence[index-2]==i) to if ((index-2>=0)&&(Sequence[index-2]==i)

The other neednot change at all!

And I get a successful AC , TimeCost 0.000s and MemorySpent low(64k).

To review the problem again,

I feel How blinkered I was!

But I'm Very Very Happy I can fit it by myself.

Thank you all the same!

Posted: **Fri Jul 22, 2005 7:48 pm**

xbeanx, how can you build an infinitely long string?

Suppose you have AB

The sequence should be..

Is there any other sequence?? I think NO.

Suppose you have AB

The sequence should be..

Code: Select all

```
A
AB
ABA
B
BA
BAB
```

Posted: **Wed Aug 10, 2005 10:59 pm**

Please give a hint or algorithm to solve this problem.

[/b]

[/b]

Posted: **Wed Aug 10, 2005 11:01 pm**

Please give a hint or algorithm to solve this problem.