306 - Cipher

[DemonCris]

I always get TLE ><

my alg. is as follows:
1. get the period of the string-change.
if the string is as the same as original
one after some changing order.
finally, I get a cycle to reduce the computing time. But I still get TLE ><

2. after the failure of the first alg., I get another alg. to solve this problem:
first, I get each cycle of each character when that appear twice. finally, I still get TLE ><...

I have enough. I hate this problem. Can someone tell me a good alg. ? Thank you very much^^

[pochmann]

No need to hate it. In fact, I think it's a very beautiful one.

In your second algorithm: When you've found the cycle of the first position, what do you do with the other positions in the cycle? Do you search their cycles again or use the information already obtained?

Stefan

[DemonCris]

Thank you very much ^^

After getting one cycle, I search again^^|||

[pc5971]

I received the message

Code: Select all

Your program has died with signal 8 (SIGFPE). Meaning:

    Floating point exception

Before crash, it ran during 0.002 seconds.

Can somebody what that means? My code is:

[c]
#include <stdio.h>
#include <string.h>

#define max 201

main()
{ int n,i,j,a;
int x[max][max];
char s[max],s1[max];
scanf("%d",&n);

while (n)
{ for (i=1;i<=n;i++)
{ x[0]=i;
scanf("%d",&x[1]);
}
for (i=1;i<=n;i++)
{ j=1;
while (x[j]!=x[0])
{ a=x[j];
j++;
x[j]=x[a][1];
}
x[0]=j;
}
scanf("%d ",&a);
while (a)
{ gets(s);
for (i=strlen(s);i<=n;i++)
{ s=' ';
s[i+1]='\0';
}
strcpy(s1,s);
for (i=0;i<strlen(s);i++)
if (x[0][i+1]!=1)
{ j=a%x[0][i+1];
if (j!=0)
{ j=x[i+1][j]-1;
s1[j]=s;
}
}
printf("%s\n",s1);
scanf("%d ",&a);
}
scanf("%d",&n);
}
}
[/c]

Thanx

[epsilon0]

j=a%x[0][i+1];

this would obviously fail if x[0][i+1] is zero.

[SilVer DirectXer]

[c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void convert(int k,int times,char []);
int num[200],times,k,i,a,j;
char string[202],dummy;
void main(void)
{

do{

scanf("%d",&times);
if (times==0)
{
feof(stdin);
break;
}
for (i=0;i<times;i++)
{
scanf("%d",num+i);
}
do
{
scanf("%d",&k);
if (k==0)
{
printf("\n");
break;
}
scanf("%c",&dummy);
gets(string);
a=strlen(string);
if (a<times)
{
for (j=a;j<=times-1;j++)
string[j]=' ';
}
string[times]='\0';

convert(k,times,string);
}while(1);

}while(1);

}

void convert(int k,int times,char string[])
{
int i,j;
char result[202];
for (i=0;i<k;i++)
{
for (j=0;j<times;j++)
{
result[num[j]-1]=string[j];
}
strncpy(string,result,times);
}
printf("%s\n",string);
}
[/c]
I got TLE,is that really my logic is running too long or....something other make my stopped at somewhere?
Thanks!

[junjieliang]

I didn't run through your code closely, but I guess it has to do with your algorithm. Note that k can be as big as possible (ignoring integer overflow) and yet your program should run in time...

[jasemty]

I didn't run through your code closely, but I guess it has to do with your algorithm. Note that k can be as big as possible (ignoring integer overflow) and yet your program should run in time...

Will k be as large as the type "long"?
Thanks.

[SilVer DirectXer]

[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int convert(int k,int times,char []);
int num[202],times,i,a,j,index[202];
long k;
char string[202],dummy,ostring[202];

int main(void)
{
int repeat;
char temp[202];
do{
scanf("%d",&times);
if (times==0)
return 0;
for (i=0;i<times;i++)
{
scanf("%d",num+i);
}

do
{
for (i=0;i<times;i++)
num--;
scanf("%d",&k);
if (k==0)
{
printf("\n");
break;
}
scanf("%c",&dummy);
gets(string);
a=strlen(string);
if (a<times)
{
for (j=a;j<=times-1;j++)
string[j]=' ';
}
string[times]='\0';
strncpy(ostring,string,strlen(string));
repeat=convert(k,times,string);
for (i=0;i<times;i++)
temp=string[index];
temp[strlen(string)]='\0';
printf("%s\n",temp);
for (i=0;i<times;i++)
num++;
}while(1);

}while(1);

}

int convert(int k,int times,char string[])
{
int i,j,KO=1;
int result[202];
for (i=0;i<times;i++)
{
index=i;
}
for (i=0;i<k;i++)
{
for (j=0;j<times;j++)
{
result[num[j]]=index[j];
}
for (j=0;j<times;j++)
{
index[j]=result[j];
}

}
return 0;
}
[/cpp]
Help....

[titid_gede]

always get TLE for this problem. is there any good method?
my algo is :
1. simulate it until find cycle. at each step i store the result in a big array.
2. after find cycle. i use mod, so that not to search again.
but TLE.
i'm pretty sure that there must be another way, since many solve this < 1 sec, even 1 solved this prob in 0:00 !

with love & light,

titid

[junjieliang]

When you do by this method, a cycle can repeat after n! permutations, which is too big. A hint, think of how you can make use of lcm...

[Dominik Michniewski]

I used the same algorithm as you, titd_gede, and got Acc in 0.301 sec ...
Maybe you have some mistakes in your code?

Best regards
DM

[titid_gede]

i do not know. but i think jungjeliang was right. that a cycle can repeat after n!. here is my main code :
[c]
strcpy (allresult[0], data);
for (i = 0; i < k; i++) {
for (j = 0; j < n; j++)
temp[key[j]-1] = allresult[j];
temp[n] = '\x0';
strcpy (allresult[i+1], temp);
if (!strcmp (temp, allresult[0]))
break;
}
[/c]
i store all in variable allresult, and it will stop after k reached or cycle found, which come first.

with love & light,

titid

[Dominik Michniewski]

Maybe you do something like this: look for a cycle for every data in block?
I do it only once at beginning of block ... maybe it's your mistake ?

Best regards
DM

[titid_gede]

yes, i look for cycle for each data.
now i change it, but now i got Memory limit Exceeded (for big array) since if i reduce size got Run time Error (sigsev)
must look for another way.

with love & light,

titid