517 - Word

[shamim]

[cpp]
Got AC
[/cpp]

[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.

[shamim]

if more than one writing rule works for a particular character,
which should i use?

[szymcio2001]

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]

[szymcio2001]

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'

[szymcio2001]

if more than one writing rule works for a particular character [...]

It's impossible.

[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

[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.

[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!

[Robert Gerbicz]

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

[gmacar]

Are there any tricky cases?
I'm always getting WA.

[gmacar]

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.

[Fransisflug]

think that judge knows better mobile spy..really deceptive

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