## 129 - Krypton Factor

Moderator: Board moderators

hnphuong
New poster
Posts: 3
Joined: Fri Oct 26, 2001 2:00 am
Location: Vietnam
Contact:
Who have either its solution or algorithm please tell me. Thank you.
arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
Just generate all the first n sequences using backtracking, and print the last one.

Kristoffer Hansen
hnphuong
New poster
Posts: 3
Joined: Fri Oct 26, 2001 2:00 am
Location: Vietnam
Contact:
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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
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
New poster
Posts: 3
Joined: Fri Oct 26, 2001 2:00 am
Location: Vietnam
Contact:
Only 501? That is amazing. Thank you for your suggestions.
xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm

### 129 - Krypton Factor

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
String should be smallest ....

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 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:

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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm

### 129 Krypton Factor Help me!!! plz

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
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm
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!
plz..........
Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage
New poster
Posts: 4
Joined: Wed Aug 10, 2005 10:43 pm
Contact:

### 129: Krypton Factor

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