Page **3** of **5**

### I really don't know why I got TLE on p306

Posted: **Fri May 13, 2005 5:20 am**

by **johnnydog33**

program p306;

type arr=array[1..500] of longint;

var n,i,k,r,j,y:longint;

a:arr;

w,get:array[1..500] of char;

ch:char;

function lcm(a,b:longint):longint;

var t:longint;

begin

if b=0 then lcm:=a else lcm:=lcm(b,a mod b);

end;

function circle(w:arr):longint;

var flag:array[1..500] of boolean;

i,k1,ans,p,e:longint;

begin

fillchar(flag,sizeof(flag),false);

ans:=1;

repeat

k1:=0;

for i:=1 to n do

if not flag* then begin*

k1:=i;

break;

end;

if k1<>0 then begin

p:=k1;e:=0;flag[p]:=true;

while a[p]<>k1 do begin

inc(e);

p:=a[p];

flag[p]:=true;

end;

e:=e+1;

if ans>e then ans:=ans*e div lcm(ans,e) else ans:=ans*e div lcm(e,ans);

end;

until k1=0;

circle:=ans;

end;

begin

repeat

readln(n);

if n<>0 then begin

fillchar(a,sizeof(a),0);

for i:=1 to n do read(a*);*

y:=circle(a);

readln;

repeat

read(k);

if k<>0 then begin

read(ch);r:=0;

fillchar(w,sizeof(w),' ');

fillchar(get,sizeof(get),' ');

while not eoln do begin

read(ch);

inc(r);

w[r]:=ch;

end;

readln;

for i:=1 to k mod y do begin

for j:=1 to n do get[j]:=w[j];

for j:=1 to n do w[a[j]]:=get[j];

end;

for i:=1 to n do write(w*);*

writeln;

end;

until k=0;

readln;

end;

writeln;

until n=0;

end.

### 306 Cipher

Posted: **Tue May 31, 2005 5:07 pm**

by **StatujaLeha**

Hi all!

I have got many times WA in this problem, but i don't know where is the mistake

Could you give me the test cases please and check up my results.

10

4 5 3 7 2 8 1 6 10 9

1 Hello Bob

2 Hello Bob

3 Hello Bob

4 Hello Bob

5 Hello Bob

6 Hello Bob

0

10

4 3 7 5 6 1 8 9 10 2

1 acm.uva.es

2 acm.uva.es

3 acm.uva.es

4 acm.uva.es

5 acm.uva.es

6 acm.uva.es

7 acm.uva.es

8 acm.uva.es

9 acm.uva.es

10 acm.uva.es

11 acm.uva.es

12 acm.uva.es

0

0

Result:

BolHeol b

lelBo Hob

HolleoB b

BelHo lob

lolBeoH b

Hello Bob

vsca.uma.e

uesva.cma.

..euvascma

aa..uvescm

vmaa.u.esc

ucmva.a.es

.scuvama.e

aes.uvcma.

v.ea.uscma

ua.va.escm

.mauva.esc

acm.uva.es

Posted: **Thu Jun 02, 2005 10:17 pm**

by **StatujaLeha**

I solved my problem and got Accepted! Thanks!

### 306 any efficient algo?

Posted: **Sun Jun 12, 2005 2:59 pm**

by **jaracz**

Hi!

Anyone knows how to speed-up this algo??

Here's my TLE code:

Code: Select all

```
#include <stdio.h>
#include <string.h>
class asd{
public:
char sign;
int value;
};
int main()
{
int n,k;
while(scanf("%d",&n)==1 && n)
{
int key[n];
char line[n];
asd szyfr[n];
for(int i = 0; i < n; i++)
scanf("%d",&key[i]);
while(scanf("%d",&k)==1 && k)
{
gets(line);int len = strlen(line);
if(strlen(line)<n)
{
for(int i = strlen(line); i < n; i++)
line[i] = ' ';
line[n] = '\0';
}
k %= len;
for(long x = 0; x < k; x++){
for(int i = 0; i < n; i++)
{
szyfr[i].sign = line[i];
szyfr[i].value = key[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < n; j++)
if(szyfr[j].value == i)
{
line[i-1] = szyfr[j].sign;
break;
}
}}
printf("%s\n",line);
line[0] = '\0';
}
printf("\n");
}
return 0;
}
```

Regards!

Posted: **Wed Jul 13, 2005 2:45 pm**

by **shamim**

I am getting WA, could some one post some test cases.

The previous cases could be wrong as it was asked when the author was getting WA.

Posted: **Wed Jul 13, 2005 4:31 pm**

by **mf**

Input:

Code: Select all

```
10
4 5 3 7 2 8 1 6 10 9
65540 CERC
1 ABCDEFGHIJ
2 ABCDEFGHIJ
3 ABCDEFGHIJ
4 ABCDEFGHIJ
5 ABCDEFGHIJ
6 ABCDEFGHIJ
7 ABCDEFGHIJ
8 ABCDEFGHIJ
9 ABCDEFGHIJ
10 ABCDEFGHIJ
11 ABCDEFGHIJ
12 ABCDEFGHIJ
13 ABCDEFGHIJ
14 ABCDEFGHIJ
15 ABCDEFGHIJ
0
0
```

My output:

Code: Select all

```
CER C
GECABHDFJI
DBCGEFAHIJ
AECDBHGFJI
GBCAEFDHIJ
DECGBHAFJI
ABCDEFGHIJ
GECABHDFJI
DBCGEFAHIJ
AECDBHGFJI
GBCAEFDHIJ
DECGBHAFJI
ABCDEFGHIJ
GECABHDFJI
DBCGEFAHIJ
AECDBHGFJI
```

Posted: **Sat Aug 13, 2005 1:02 pm**

by **Jan**

Find the k-th permutation of the values first. The rest is simple.

Posted: **Sat Aug 13, 2005 4:23 pm**

by **jaracz**

you're right:)

wasn't necessery to change string each time

thanks anyway

<peace>

Posted: **Sun Aug 14, 2005 11:18 am**

by **jaracz**

Actually, your suggestion gives TLE too

there is 2kn operations to get the final sequence and than print them

maybe you did it in better way??

I tried to speed up it several times but it must be k-permutaion, otherwise i get WA;(

anyway here is my code

Code: Select all

```
#include <stdio.h>
#include <string.h>
int main()
{
int n,k,counter = 0;char line[201];
while(scanf("%d",&n)==1 && n)
{
if(counter)printf("\n");
else counter = 1;
int key[n],seq[n],pom[n];
for(int i = 0; i < n; i++)scanf("%d",&key[i]);
while(scanf("%d ",&k)==1 && k)
{
gets(line);
if(strlen(line)<n)
{
for(int i = strlen(line); i < n; i++)
line[i] = ' ';
line[n] = '\0';
}
for(int i = 0; i < n; i++)pom[i] = i+1;
for(int c = 0; c < k; c++)
{
for(int i = 0; i < n; i++)seq[key[i]-1] = pom[i];
for(int i = 0; i < n; i++)pom[i] = seq[i];
}
for(int i = 0; i < n; i++)
printf("%c",line[seq[i]-1]);
printf("\n");
}
}
return 0;
}
```

Any other suggestions??

Posted: **Fri Sep 02, 2005 9:03 am**

by **trulo17**

Code: Select all

```
#include<cstdio>
#include<cstring>
int main()
{
int n,i,j,ciclo,t,k;
int T[210][210];
int A[210];
char S[210],S2[210];
char c;
for( i = 0; i < 210; ++i )
{
T[0][i] = i;
}
for( ; ; )
{
scanf( "%d", &n );
if( n == 0 )
{
break;
}
for( i = 0; i < n; ++i )
{
scanf( "%d", &A[i] );
}
/*problematic part
for( i = 1; ; ++i )
{
for( j = 0; j < n; ++j )
{
T[i][ A[j] - 1 ] = T[ i - 1 ][j];
}
for( j = 0; j < n; ++j )
{
if( T[i][j] != j )
{
break;
}
}
if( j == n )
{
break;
}
}*/
ciclo = i;
for( ; ; )
{
scanf( "%d%c", &k,&c );
if( k == 0 && c == '\n' )
{
break;
}
gets( S );
for( i = strlen( S ); i < n; ++i )
{
S[i] = ' ';
}
S[i] = '\0';
t = k % ciclo;
for( i = 0; i < n; ++i )
{
S2[i] = S[ T[t][i] ];
}
S2[i] = '\0';
puts( S2 );
}
putchar( '\n' );
}
}
```

I can`t see why i am getting tle once and again( because it's supossed cycle <= 200. any suggestions?

### RTE

Posted: **Thu Jan 12, 2006 6:25 pm**

by **mamun**

Oh! This is irritating! RTE.

From other posts, I think I can take it for sure that the cycle is less than 200. But I'm getting RTE.

I use gets() to read input. So I consider the input is as exactly as in the description, ie. n is given in one line, the n integers in next line, k and a message in each line and a 0 in last line of each block. And there is no blank line. I think I should better post my code. Any help is greatly appreciated.

Posted: **Wed Feb 01, 2006 11:26 pm**

by **mamun**

Would anybody give a look at my code above plz?

Posted: **Thu Feb 02, 2006 11:32 am**

by **mf**

Input:

Code: Select all

```
28
2 1 4 5 3 7 8 9 10 6 12 13 14 15 16 17 11 19 20 21 22 23 24 25 26 27 28 18
2006 microsoft.com
0
0
```

Output:

Posted: **Thu Feb 02, 2006 3:14 pm**

by **mamun**

Thank you mf.

Hmm... Segmentation fault. So it is not that cycle is less than 200 or is it that my coding is faulty? If the first case is true then what should be the idea for solving?

Posted: **Thu Feb 02, 2006 5:33 pm**

by **mf**

I guess, by cycle of a permutation pi, you meant the smallest integer c>0, such that for all x, pi^c (x) = x. This number is usually called

*order* of permutation, and in this problem it could be as large as 24067258815600.

There are several correct ways to solve this problem.

1. You can use the fact, that composition of permutations is associative, and binary exponentiation to get O(n log k) algorithm.

2. Write permutation in cyclic notation (if you don't know what it is, look in

google.) If an element x is in a cycle of length c, then pi^k (x) = pi^{k mod c} (x). You can use this to compute pi^k in O(n) time.

For example, in the sample input, you are given a permutation pi=(1 4 7)(2 5)(3)(6 8)(9 10). How do you compute, say pi^1995 (5) from it? Element 5 is in a cycle of length 2, so after every 2 applications of pi it returns to its original place, so pi^1995 (5) = pi^(1995 mod 2) (5) = pi^1 (5) = 2. Hence, after 1995 encodings of CERC, the 5th character (a space) is put to position 2.