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

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 3:20 pm

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
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 » Fri May 23, 2003 8:44 am

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

Haomiao
New poster
Posts: 5
Joined: Sat Nov 16, 2002 11:28 am
Location: Xi'an,China
Contact:

how can i use lcm in 306

Post by Haomiao » Sat May 24, 2003 5:13 am

i always get TLE,too
help...

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

Post by Dominik Michniewski » Mon May 26, 2003 7:28 am

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
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 » Tue May 27, 2003 5:23 pm

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

thank you very much.

with love & light,

titid
Last edited by titid_gede on Fri Aug 29, 2003 6:33 am, edited 1 time in total.
Kalo mau kaya, buat apa sekolah?

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

Post by Rav » Mon Aug 25, 2003 10:37 am

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]
Rafał Sokołowski

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

Post by Dominik Michniewski » Mon Aug 25, 2003 12:26 pm

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

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf » Fri Sep 12, 2003 9:09 am

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Wed Jun 16, 2004 12:09 am

Dominik Michniewski wrote: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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Wed Jun 16, 2004 6:29 am

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

PS: my code is 855 bytes, but without comments :lol:

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

306 cipher rte!!!

Post by trulo17 » Sun Jan 30, 2005 9:23 am

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' );
    }
}

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

Post by Ali Arman Tamal » Mon Feb 07, 2005 12:19 pm

I am getting WA :cry:

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Mar 02, 2005 2:04 am

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Mar 02, 2005 2:07 am

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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

306 RE help

Post by oulongbin » Sat Mar 05, 2005 11:01 am

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; 
} 

Post Reply

Return to “Volume 3 (300-399)”