306 - Cipher

[Dominik Michniewski]

It's strange, beacuase I use arrays only for 205 elements.... So I think, that you must have mistake in your code ...

Best regards
DM

[titid_gede]

i have changed my algorithm, and it uses only 2 dimension array 205*205 to store the cycle. but now i got WA in 0.217 Sec. What is the trickies input here? how is the upper limit for k?

with love & light,

titid

[Haomiao]

i always get TLE,too
help...

[Dominik Michniewski]

I think that's no upper limit for k.
You must find cycles and it's all ... If you still coudn't get Acc, you can send me your code, titid_gede ...

Best regards
DM

[titid_gede]

sorry for late reply. here is my code :
[c]
--- cutted----
[/c]

thank you very much.

with love & light,

titid

[Rav]

hi i got TL too. but i thing my algo i good. can cycle be larger then long int ?
here is my algo to find cycle:

[cpp]
long int euklid (long int x,long int y) /* biggest common factor. (this function is good i think */
{
long int g=1,t;
while ((x%2==0) && (y%2==0))
{
x/=2;
y/=2;
g*=2;
}
while (x>0)
{
if (x%2==0)
x/=2;
else if (y%2==0)
y/=2;
else
{
t=abs(x-y)/2;
if (x>=y)
x=t;
else
y=t;
}
}
return g*y;
}

long int findcycle() /* function finding cycle*/
{
int wsk,wart,cycle=1,c1,c2,podz;
wart=tab[tab[1]];
while (wart!=tab[1])
{
wart=tab[wart];
++cycle;
}
for (wsk=2;wsk<=wielkosc_tab;++wsk)
{
c1=1;
wart=tab[tab[wsk]];
while (wart!=tab[wsk])
{
wart=tab[wart];
++c1;
}
podz=euklid(cycle,c1);
cycle=(int)((cycle*c1)/podz);
}
return cycle;
}
[/cpp]

[Dominik Michniewski]

I don't use GCD (Greatest Common Divisor) in this problem , and my code has 1011 bytes in all (with all comments and so on ... )
I don't think that cycle length will be larger than range of long int ...

I simple find cycles (in O(N^2) time) and find right positions for every character in input with the same time-complexity ....

HINT: cycle length couldn't be longer than 200

Best regards
DM

[b3yours3lf]

my prog got tLE too, my algorithm same as algorithm above, find the cycle first then mod the loop form input..
here's my code
[c]#include<stdio.h>
#include<string.h>

int same(char text[], int n)
{
int i;
for(i=0;i<n;i++)
if(text!=i+1) return 0;
return 1;
}

main()
{
int nkey, key[200], loop, lp, idx;
int i, j, len, ptr1, ptr2;
char text[2][210], temp[210];
#ifndef ONLINE_JUDGE
freopen("306.in","r",stdin);
freopen("306.out","w",stdout);
#endif
while(scanf("%d",&nkey)==1)
{
if(nkey==0) break;
for(i=0;i<nkey;i++) scanf("%d",&key);
/* check the min loop */
for(i=0;i<nkey;i++)
text[0]=i+1;
text[0]='\0';

ptr1=0;
ptr2=1;

for(i=0; ;i++)
{
for(j=0;j<nkey;j++)
text[ptr2][key[j]-1]=text[ptr1][j];
ptr1^=ptr2^=ptr1^=ptr2;
if(same(text[ptr1], nkey)) break;
}
lp=i+1;

while(scanf("%d ",&loop)==1)
{
if(loop==0) break;
loop%=lp;
gets(temp);
len=strlen(temp);
for(i=len;i<nkey;i++) temp=' ';
temp='\0';
strcpy(text[0],temp);
text[0]='\0';
text[1]='\0';

ptr1=0;
ptr2=1;

for(i=0;i<loop;i++)
{
for(j=0;j<nkey;j++)
text[ptr2][key[j]-1]=text[ptr1][j];
ptr1^=ptr2^=ptr1^=ptr2;
}
printf("%s\n",text[ptr1]);
}
}
return 0;
}[/c]

[minskcity]

I don't use GCD (Greatest Common Divisor)
HINT: cycle length couldn't be longer than 200

I've just got TLE on this problem 3rd time. Can you explain your algorithm? I don't see a way to do this problem fast enough without using GCD.

If you are given a string : "a {48 spaces} b {49 spaces} ";
transformantions:
1->2 //// 50->51
2->3 //// 51->52
........ //// ...........
49->1 //// 99->50

The cycle length will be 49*50 = 2450 > 200;
It's possible to show that cycle length can be REALLY big for this problem.
PLEASE, anybody who solved this problem, let me know how to do it.

thx.

[minskcity]

Never mind. Cycles for each position are at most 200.

PS: my code is 855 bytes, but without comments

[trulo17]

i read at forum that the maximum cycle is 200, so could somebody explain me why does this get rte ? i think this could get wa or tle but not rte. i hope somebody can help.

Code: Select all

#include<cstdio>
#include<cstring>
int main()
{
    int n,m,i,j;
    int A[200];
    char T[202][201];
    for( ; ; )
    {
        scanf( "%d", &n );
        if( n == 0 )
        {
            break;
        }
        for( i = 0; i < n; ++i )
        {
            scanf( "%d", &A[i] );
            --A[i];
        }
        for( ; ; )
        {
            scanf( "%d", &m);
            if( m == 0 )
            {
                break;
            }
            scanf( " " );
            gets( T[0] );
            for( j = strlen( T[0] ); j < n; ++j )
            {
                T[0][j] = ' ';
            }        
            T[0][n] = '\0';
            for( i = 1; ; ++i )
            {
                for( j = 0; j < n; ++j )
                {
                    T[i][ A[j] ] = T[i - 1][j];
                }
                T[i][n] = '\0';
                if( strcmp( T[0], T[i] ) == 0 )
                {
                    break;
                }
            }
                puts( T[m % i] );
        }
        putchar( '\n' );
    }
}

[Ali Arman Tamal]

I am getting WA

Someone please post some test cases. All the cases I generated were correct, but still WA

[Sedefcho]

for( i = 1; ; ++i )
{
for( j = 0; j < n; ++j )
{
T[ A[j] ] = T[j];
}
T[n] = '\0';
if( strcmp( T[0], T ) == 0 )
{
break;
}
}

The external cycle here ...
for( i = 1; ; ++i )



It may iterate many many times thus giving you a value for I which
is far beyond 201 ( you declare T as int[202][201] )


Don't you think so ?

Actually you try to simulate the process they describe
in the problem statement, but I am pretty sure this is
not the right approach for that problem.

You should try to find the numbers of steps S after which the
permutation of the N integers given ( in the second line of
each input test case ) goes/maps back to itself without
simulating the process ( applying A, then again A, then again A
and so on until you get a permutation equal to the first one ).

Reading some introduction to Group Theory
( even the first few pages ) should be enough.
That is my personal opinion of course about this
problem. I haven't tried it yet. I think it is not fully
about simulation.

[Sedefcho]

By the way even if you simulate the problem you don't
need so large table T.

You need just two ot tree "lines"
( one-dimensional arrays, strings ) of it.

Like T_0, T_PREV, T_CURR

You simulate until
T_CURR = T_0 ,
for each I=0,1...199 .

But this way you will get TLE, I guess.

[oulongbin]

i always get RE,if i enlarge the cycle[][],i get TLE,could someone tell me what's wrong with my code ?thanks.

Code: Select all

#include "stdafx.h"
#include <iostream> 
using namespace std; 
#include <cstring>


int main() 
{
	char cycle[205][205];
	int ci;
	int sq[205];
	int n;
	int sum;
	int ts;
	char f[205];
	char tf[205];
	int len;
	int i,j;
	int cnt;

	while(cin>>n && n!=0)
	{
		for(i=0;i<n;i++)
			cin>>sq[i];
		
		while(cin>>sum && sum!=0)
		{
			cin.get();
			cin.getline(f,205);
			len=strlen(f);
			
			if(len<n)
			{
				for(i=len;i<n;i++)
					f[i]=' ';
				f[i]='\0';
			}
			
			ci=0;
			strcpy(cycle[ci++],f);
			tf[n]='\0';
			ts=sum;
			cnt=0;
			while(sum--)
			{
				for(i=0;i<n;i++)
				{
					tf[sq[i]-1]=f[i];
				}
				for(j=0;j<ci;j++)
				{
					if(!strcmp(tf,cycle[j]))
						break;
				}
				if(j!=ci)
					break;
				strcpy(cycle[ci++],tf);
				strcpy(f,tf);
				cnt++;
			}
			
			if(sum>0)
			{
				cout<<cycle[j+(ts-cnt)%(ci-j)-1]<<endl;
			}
			else
				cout<<f<<endl;
		}
		cout<<endl;
	}
	return 0; 
}