Page 1 of 5

Posted: Tue Feb 26, 2002 7:09 pm
by 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^^

Posted: Wed Feb 27, 2002 6:36 am
by 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

Posted: Wed Feb 27, 2002 3:01 pm
by DemonCris
Thank you very much ^^

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

306 What that means???

Posted: Fri Nov 15, 2002 7:50 am
by 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

Posted: Fri Dec 13, 2002 10:26 pm
by epsilon0
j=a%x[0][i+1];

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

ACM 306

Posted: Sun Jan 26, 2003 9:56 am
by 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!

Posted: Mon Jan 27, 2003 1:38 pm
by 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...:)

How large can K be?

Posted: Sat Feb 01, 2003 4:08 pm
by jasemty
junjieliang wrote: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. :o

306TLE

Posted: Wed Feb 05, 2003 5:56 pm
by 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....

306 - Cipher

Posted: Sat May 17, 2003 5:44 am
by 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

Posted: Sat May 17, 2003 2:49 pm
by 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...

Posted: Mon May 19, 2003 7:47 am
by 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

Posted: Mon May 19, 2003 9:01 am
by 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

Posted: Mon May 19, 2003 12:11 pm
by 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

Posted: Mon May 19, 2003 3:04 pm
by 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