306 - Cipher

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

Moderator: Board moderators

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Tue Feb 26, 2002 7:09 pm

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
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by pochmann » Wed Feb 27, 2002 6:36 am

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

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Wed Feb 27, 2002 3:01 pm

Thank you very much ^^

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

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

306 What that means???

Post by pc5971 » Fri Nov 15, 2002 7:50 am

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

Post by epsilon0 » Fri Dec 13, 2002 10:26 pm

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

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

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

ACM 306

Post by SilVer DirectXer » Sun Jan 26, 2003 9:56 am

[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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Jan 27, 2003 1:38 pm

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
New poster
Posts: 2
Joined: Sat Jan 11, 2003 11:07 am
Location: Hong Kong

How large can K be?

Post by jasemty » Sat Feb 01, 2003 4:08 pm

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

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

306TLE

Post by SilVer DirectXer » Wed Feb 05, 2003 5:56 pm

[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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

306 - Cipher

Post by titid_gede » Sat May 17, 2003 5:44 am

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
Kalo mau kaya, buat apa sekolah?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat May 17, 2003 2:49 pm

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

Post by Dominik Michniewski » Mon May 19, 2003 7:47 am

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
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)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Mon May 19, 2003 9:01 am

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
Kalo mau kaya, buat apa sekolah?

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

Post by Dominik Michniewski » Mon May 19, 2003 12:11 pm

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
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)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Mon May 19, 2003 3:04 pm

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
Kalo mau kaya, buat apa sekolah?

Post Reply

Return to “Volume 3 (300-399)”