Page 1 of 1

517 - Word

Posted: Sat Jun 21, 2003 9:04 am
by shamim
[cpp]
Got AC
[/cpp]

Posted: Sun Jun 22, 2003 9:25 am
by shamim
ok then, could any one explain to me what this means,
As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.
thanks.

Posted: Mon Jun 23, 2003 8:32 am
by shamim
if more than one writing rule works for a particular character,
which should i use? :o

Re: 517 Word

Posted: Tue Jul 06, 2004 11:18 am
by szymcio2001
shamim wrote: could someone give me a few more test cases.
Thanks.

Code: Select all

  
16
aabaabbaababbbba
aaab
aaba
abab
abba
baaa
babb
bbab
bbba
2000000000
My Acc solution gives:

Code: Select all

aabbbbbbabbbbbbb
[/code]

Posted: Tue Jul 06, 2004 11:21 am
by szymcio2001
shamim wrote:ok then, could any one explain to me what this means,
As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.
For example - if your computet output is 'bbaaba' you should output it as 'aababb'

Posted: Tue Jul 06, 2004 11:23 am
by szymcio2001
shamim wrote:if more than one writing rule works for a particular character [...]
It's impossible.

517 Word what it means??

Posted: Wed Jun 07, 2006 11:37 am
by feanor
"Rewriting rules rewrite a letter at a position i, depending on letters at the positions i - 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps? "

i've understand how to apply a single rules. but what my program have to do with the eight rules? on the first step it will apply the first rule on the first character, then the first rules on the second character, then... . on second step it will apply the second rule on the first character, ... . i don't understand what i've to do!

anyone want to help me?

thanks

Posted: Sun Jun 25, 2006 8:43 pm
by the LA-Z-BOy
You need exactly 8 rules here....
Because your change of character depends on 3 characters... ( |{a,b}| = 2 and dependency on 3 chars that's 2^3 = 8 ), that's why there are 8 rules.
At first step ( or whatever step) ... you should apply those rules which is applicable there... not the first rule only... because you have to apply multiple rules if the characters are different ...
like
abaab
for first character you need rule like
aabX (abaab)
for second character you need rule
bbaX (abaab)
for the third character
aaaX (abaab)
and so on....
[X = a or b whatever in the input]
Hope this helps.

517.- WA Problem

Posted: Thu Jan 10, 2008 10:45 pm
by Javo
Hi everybody!

I have a problem with this, I had built a case generator and compare with a brute force program and always obtained the correct answer but... I don`t get AC!

Code: Select all


/*UVa 517.- Word*/
/*Javier Alvarez Morales*/
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int M=0;

unsigned int Pow2[17]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536}; /*I don`t have calculated every time :)*/
char Past[65537][17]; /*Past configurations*/
unsigned int Top;
long  int Whereis[131073]; /*Where is saved the array*/
long int CycleR;   /*Every ? the numbers repited*/
long int Since; /*Since every permutation start the CycleR*/
char Word[17],WordR[17];
char *W,*WR;
char Rules[8][6]; /*Rules of L-System*/
int n;   /*Max lenght of string*/
unsigned long int s;
/*Function that calculate the position in a dictionary lexicographycally ordened*/
unsigned long int CalculaPos(int ini){
    unsigned int Pos=0;
    register int i;
    for( i=0 ; i<n ; i++ )
       if( WR[ (ini+i)%n ] == 'b' )
          Pos += Pow2[ (n-i-1) ];
    return Pos;
}
void Desplaza(int d){
     int i;
     for( i=0; i<n ; i++ )
        W[i] = WR[ (d+i)%n ];
     W[n] = '\0';
}
void Best_Lexico(){
     int i;
     unsigned long int nRule;
     unsigned int Min,D;
     nRule=0;
     Min=32768;
     for( i=0 ; i<n ; i++){
        nRule = CalculaPos(i);
        if( nRule < Min ){
           Min=nRule;
           D=i;
        }
     }
     Desplaza(D);
     if( Whereis[ Min ] != -1 ){ /*Already exist this permutation*/
        CycleR = Top - Whereis[ Min ];
        Since = Whereis[ Min ];
     }else{
         /*Save result*/
         strcpy( Past[Top], W );
         Whereis[ Min ] = Top;
         ++Top; 
     }
}
void Transform(){
     register int i;
     unsigned int nRule;
     char *aux;
     for( i=0 ; i<n ; i++ ){
          nRule=0;
          if( W[ (i-2+n)%n ] == 'b' )
              nRule += 4;
          if( W[ i ] == 'b' )
              nRule += 2;
          if( W[ (i+1)%n ] == 'b' )
              nRule += 1;
          WR[i] = Rules[nRule][3];
     }
     WR[n] = '\0';
     Best_Lexico();
     /*Interchange the strings*/
     aux = W;
     W = WR;
     WR = aux;
}
void ReiniciaVars(){
     Top=0;
     CycleR = -1;
     Since = 0;
     memset( Whereis, -1 ,Pow2[n]*sizeof(unsigned int) );
}
int main(){
  unsigned long int i;  
  W = Word;
  WR = WordR;
  char *aux;
  unsigned int WhichOne;
  while( 0 < scanf("%d ",&n) ){
     ReiniciaVars();
     scanf("%s ",W);
     for( i=0 ; i<8 ; i++ )
        scanf("%s ",Rules[i]);
     scanf("%lu ",&s);
     if( !s ){ /*In case of don't need to aply any transformation, only choise the least lexicographically*/
        aux = W;
        W = WR;
        WR = aux;
        Best_Lexico();  
        /*Interchange the strings*/
        aux = W;
        W = WR;
        WR = aux;
     }
     for( i=0 ; i<s ; i++ ){
        if( CycleR > 0 ) break;
        Transform();
        M?printf(">%s\n",WR):1;
     }
     if( CycleR > 0 ){
         WhichOne = Since  + ( (s - Since -1)%CycleR );
         M?printf("since=%d,CycleR=%lu\n",Since,CycleR):1;
         printf("%s\n",Past[WhichOne]);  
     }else
        printf("%s\n",WR);  
  }
  return 0;
}

Maybe the input is tricky ? :-?

Anybody can help me? thanks a lot! :)

Re: 517 Word

Posted: Sat Feb 09, 2008 12:06 pm
by Robert Gerbicz
szymcio2001 wrote:
shamim wrote: could someone give me a few more test cases.
Thanks.

Code: Select all

  
16
aabaabbaababbbba
aaab
aaba
abab
abba
baaa
babb
bbab
bbba
2000000000
My Acc solution gives:

Code: Select all

aabbbbbbabbbbbbb
[/code]
That's bad input, since from the problem statement:

Code: Select all

2 < n < 16 the length of the input

Re: 517.- WA Problem

Posted: Mon Aug 24, 2009 3:22 pm
by gmacar
Are there any tricky cases?
I'm always getting WA.

Re: 517.- WA Problem

Posted: Tue Aug 25, 2009 1:00 pm
by gmacar
gmacar wrote:Are there any tricky cases?
I'm always getting WA.
After a week, the judge has accepted my solution.
Guys, watch out... the output for s=0 can be deceptive. :cry:

Re: 517.- WA Problem

Posted: Tue Sep 06, 2011 10:43 am
by Fransisflug
think that judge knows better mobile spy..really deceptive :cry:

Re: 517 - Word

Posted: Sun Feb 11, 2018 4:12 am
by metaphysis
Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    string rule[8] = {"aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"};
    
    for (int c = 1; c <= 100; c++)
    {
        int n = rand() % 16;
        if (n <= 3) n = 3;
        
        cout << n << '\n';
        for (int i = 1; i <= n; i++)
            cout << (char)('a' + rand() % 2);
        cout << '\n';
        
        for (int i = 0; i < 8; i++)
        {
            cout << rule[i] << (char)('a' + rand() % 2) << '\n';
        }
        
        cout << rand() % 2000000000 << '\n';
    }
    
    return 0;
}