129 - Krypton Factor

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

hnphuong
New poster
Posts: 3
Joined: Fri Oct 26, 2001 2:00 am
Location: Vietnam
Contact:

Post by hnphuong »

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:

Post by arnsfelt »

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:

Post 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 ?
arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post 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
hnphuong
New poster
Posts: 3
Joined: Fri Oct 26, 2001 2:00 am
Location: Vietnam
Contact:

Post by hnphuong »

Only 501? That is amazing. Thank you for your suggestions.
xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

129 - Krypton Factor

Post 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!
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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
Location: Newfoundland, Canada (St. John's)

Post 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!
epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

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

Post 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 !!!!
Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm

Post 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..........
Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm

Post 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!
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post 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. :)
Ami ekhono shopno dekhi...
HomePage
S M Adnan
New poster
Posts: 4
Joined: Wed Aug 10, 2005 10:43 pm
Location: Dhaka, Bangladesh
Contact:

129: Krypton Factor

Post by S M Adnan »

Please give a hint or algorithm to solve this problem.
[/b]
Hul Hul
S M Adnan
New poster
Posts: 4
Joined: Wed Aug 10, 2005 10:43 pm
Location: Dhaka, Bangladesh
Contact:

129: Krypton Factor

Post by S M Adnan »

Please give a hint or algorithm to solve this problem.
Hul Hul
Post Reply

Return to “Volume 1 (100-199)”