517 - Word

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

517 - Word

Post by shamim » Sat Jun 21, 2003 9:04 am

[cpp]
Got AC
[/cpp]
Last edited by shamim on Wed Jul 07, 2004 8:38 am, edited 1 time in total.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Jun 22, 2003 9:25 am

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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Jun 23, 2003 8:32 am

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

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Re: 517 Word

Post by szymcio2001 » Tue Jul 06, 2004 11:18 am

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]

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Tue Jul 06, 2004 11:21 am

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'

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Tue Jul 06, 2004 11:23 am

shamim wrote:if more than one writing rule works for a particular character [...]
It's impossible.

feanor
New poster
Posts: 3
Joined: Tue Jun 06, 2006 12:17 pm

517 Word what it means??

Post by feanor » Wed Jun 07, 2006 11:37 am

"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

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sun Jun 25, 2006 8:43 pm

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.
Istiaque Ahmed [the LA-Z-BOy]

Javo
New poster
Posts: 3
Joined: Thu Jan 10, 2008 10:36 pm
Location: Mexico

517.- WA Problem

Post by Javo » Thu Jan 10, 2008 10:45 pm

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 517 Word

Post by Robert Gerbicz » Sat Feb 09, 2008 12:06 pm

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

gmacar
New poster
Posts: 5
Joined: Thu May 18, 2006 9:44 am

Re: 517.- WA Problem

Post by gmacar » Mon Aug 24, 2009 3:22 pm

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

gmacar
New poster
Posts: 5
Joined: Thu May 18, 2006 9:44 am

Re: 517.- WA Problem

Post by gmacar » Tue Aug 25, 2009 1:00 pm

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:

Fransisflug
New poster
Posts: 2
Joined: Tue Sep 06, 2011 10:38 am

Re: 517.- WA Problem

Post by Fransisflug » Tue Sep 06, 2011 10:43 am

think that judge knows better mobile spy..really deceptive :cry:

metaphysis
Experienced poster
Posts: 128
Joined: Wed May 18, 2011 3:04 pm

Re: 517 - Word

Post by metaphysis » Sun Feb 11, 2018 4:12 am

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

Post Reply

Return to “Volume 5 (500-599)”