Page 1 of 2

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

Posted: Sat Oct 27, 2001 12:30 am
by arnsfelt
Just generate all the first n sequences using backtracking, and print the last one.

Kristoffer Hansen

Posted: Sat Oct 27, 2001 6:29 am
by 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 ?

Posted: Sat Oct 27, 2001 12:32 pm
by 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

Posted: Mon Oct 29, 2001 6:59 am
by hnphuong
Only 501? That is amazing. Thank you for your suggestions.

129 - Krypton Factor

Posted: Fri Sep 05, 2003 11:42 am
by 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!

Posted: Fri Sep 05, 2003 1:30 pm
by Dominik Michniewski
String should be smallest ....

Best regards
DM

Posted: Fri Sep 05, 2003 1:54 pm
by 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!

Posted: Tue Sep 09, 2003 10:57 pm
by 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.

129 Krypton Factor Help me!!! plz

Posted: Sat Oct 16, 2004 2:43 pm
by 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 !!!!

Posted: Mon Oct 18, 2004 8:14 am
by 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..........

Posted: Wed Oct 20, 2004 6:57 am
by 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!

Posted: Fri Jul 22, 2005 7:48 pm
by 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. :)

129: Krypton Factor

Posted: Wed Aug 10, 2005 10:59 pm
by S M Adnan
Please give a hint or algorithm to solve this problem.
[/b]

129: Krypton Factor

Posted: Wed Aug 10, 2005 11:01 pm
by S M Adnan
Please give a hint or algorithm to solve this problem.