129  Krypton Factor
Moderator: Board moderators

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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 squarefree 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 squarefree string, but I don't know how to output it correctly.
Thanks to everyone!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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!
xbeanx wrote:
"For this problem, I know how to build an infinitely long squarefree 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 squarefree 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
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 ((rangej>=0)&&(rangeji>=0))
{
if (Sequence[rangej]==Sequence[rangeji])
{
mark++;
}
else
{
break;
}
}
else
{
break;
}
}
if (mark==i)
return 0;
}
return 1;
}
int backdating(int index)
{
if (num>=n)
{
last = index1;
return 1;
}
for (int i=0; i<L; i++)
{
if (Sequence[index2]==i)
continue;
Sequence[index1] = i;
if (isHard(i, index1)>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!=last1)
{
cout<<endl;
j = 0;
k = 0;
}
}
else
{
if (i!=last1)
{
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 ((rangej>=0)&&(rangeji>=0))
{
if (Sequence[rangej]==Sequence[rangeji])
{
mark++;
}
else
{
break;
}
}
else
{
break;
}
}
if (mark==i)
return 0;
}
return 1;
}
int backdating(int index)
{
if (num>=n)
{
last = index1;
return 1;
}
for (int i=0; i<L; i++)
{
if (Sequence[index2]==i)
continue;
Sequence[index1] = i;
if (isHard(i, index1)>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!=last1)
{
cout<<endl;
j = 0;
k = 0;
}
}
else
{
if (i!=last1)
{
cout<<" ";
j = 0;
k++;
}
}
}
}
cout<<endl;
cout<<last<<endl;
}
return 0;
}
////////////////////////////////////////////////////////////////////////////////////
i don't understand ...is it wrong answer?
help me !!!!
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[index2]==i) to if ((index2>=0)&&(Sequence[index2]==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[index2]==i) to if ((index2>=0)&&(Sequence[index2]==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!
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
Ami ekhono shopno dekhi...
HomePage
HomePage