129 - Krypton Factor

[hnphuong]

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

[arnsfelt]

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

Kristoffer Hansen

[hnphuong]

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 ?

[arnsfelt]

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

[hnphuong]

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

[xbeanx]

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!

[Dominik Michniewski]

String should be smallest ....

Best regards
DM

[xbeanx]

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:

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

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!

[epsilon0]

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.

[Zhls]

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 !!!!

[Zhls]

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..........

[Zhls]

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!

[Jan]

xbeanx, how can you build an infinitely long string?

Suppose you have AB
The sequence should be..

Code: Select all

A
AB
ABA
B
BA
BAB

Is there any other sequence?? I think NO.

[S M Adnan]

Please give a hint or algorithm to solve this problem.
[/b]

[S M Adnan]

Please give a hint or algorithm to solve this problem.