10098 - Generating Fast

[ancaacm]

thanks, ya it was this.

[ancaacm]

Hy, anyone knows if there is another algorithm like backtracking which does the same thing only faster ?. Because I used it in 10098 and 195(verry similar with 10098) problems and it's working too slow, it's taking too much time to run, so I got to use something else but I don't know what.
my algorithm is this:

-step1: read the string from input;
- step2: order him ascending(A>a);
step 3: -permutations(strlen(string));
-step 4: when he finds a solution, you verify if it's good(hasn't been listed yet,etc. )
- step 5: if so, you list the solution
-step 6: if not go to step 3 while he finds all posible solutions;

ya, it's working fine, but not in the needed time.

Anyone has an ideea how to make this algorithm faster, or if you got another..... ?

thanks.

[Zuza]

You could do two things: optimise your check which asks has that permutation been listed or you can write an algorithm that doesn't even need to check that. Consider this: when you have a string "aab" you repeat the "aab" only if you place two "a"s on the same position in the generation. Try to avoid that from taking place.

[eg_frx]

or if you use C++, you can be a lazy programer with the help of STL functions sort and next_permutation.

[Antonio Ocampo]

Hi

This is my AC program for 10098

[cpp]

(cut)

[/cpp]

I wish I overcame Anagram (Problem 195). Do I have to do some changes in this code??

By the way, I'm a very lazy programmer . Thanks in advance

[Antonio Ocampo]

I found the mistake . I just changed this part of code:

[cpp]
n=strlen(array);

sort(array,array+n);

do
....
while( next_permutation(array,array+n) );
[/cpp]

by this

[cpp]
n=strlen(array);

sort(array,array+n,compare);

do
....
while( next_permutation(array,array+n,compare) );
[/cpp]

Where my function compare is

bool compare(char x, char y)
{
...
//In this problem we must assume that 'A'<'a'<'B'<'b'.
}

[qndel]

This is my code:

type
literka= record
z:char;
wsk:byte;
end;

lista= array[0..10] of literka;

slowo= record
tab:array[1..10] of char;
poz:byte;
level:byte;
znaki:lista;
end;


var
stos:array[1..20] of slowo;
pokaz:array[1..10] of slowo;
dl,il,i,n:word;
lp:integer;
t:string;


procedure swap(a,b:byte);
var
z:char;
begin
z:=t[a];
t[a]:=t;
t:=z;
end;


procedure sortuj;
var
i,j:byte;
begin
for i:=1 to dl do
for j:=1 to dl-i do
if t[j]>t[j+1] then
swap(j,j+1);
end;

procedure pop(var co:slowo);
begin
co:=stos[il];
dec(il);
end;

procedure pusch(co:slowo);
begin
inc(il);
stos[il]:=co;
end;

procedure wyswietl;
var
s:string;
j,i:integer;
begin
s:='';

for i:=1 to lp-1 do
begin
for j:=1 to dl do
s:=s+pokaz.tab[j];
s:=s+chr(13)+chr(10);
end;
if lp>0 then
for j:=1 to dl do
s:=s+pokaz[lp].tab[j];
writeln(s);
lp:=0;
end;


procedure wypisz(co:slowo);
begin
inc(lp);
pokaz[lp]:=co;
if lp=10 then
wyswietl;
end;


procedure rob;
var
i:word;
akt,nowe:slowo;
begin
il:=1;
stos[1].level:=1;
for i:=0 to dl do
begin
stos[1].znaki.wsk:=i+1;
stos[1].znaki.z:=t
end;
stos[1].znaki[dl].wsk:=0;
stos[1].poz:=0;
while il<>0 do
begin
pop(akt);
nowe:=akt;
akt.poz:=akt.znaki[akt.poz].wsk;
if akt.znaki[akt.poz].wsk<>0 then
pusch(akt);
nowe.tab[nowe.level]:=nowe.znaki[nowe.znaki[nowe.poz].wsk].z;
nowe.znaki[nowe.poz].wsk:=nowe.znaki[nowe.znaki[nowe.poz].wsk].wsk;
inc(nowe.level);
nowe.poz:=0;
if nowe.level=dl+1 then
wypisz(nowe)
else
pusch(nowe);
end;
end;

begin
readln(n);
for i:=1 to n do
begin
readln(t);
dl:=length(t);
if dl>10 then
halt;
lp:=0;
sortuj;
rob;
wyswietl;
end;
end.


If you see any mistakes please tell me about them!!!!

[Zuza]

Input:

Code: Select all

1
aaa

Your Output:

Code: Select all

aaa
aaa
aaa
aaa
aaa
aaa

Correct Output:

Code: Select all

aaa

Two identical permutations muss not be printed...

[Jemerson]

Getting WA's maybe my compare method is not working as desired, can anyone help me?

Code: Select all

CUT AFTER ACC.
}

[chunyi81]

By reading your code, without even running the code, I see one possible cause of the WA.

Your char array is declared as follows:

Code: Select all

char s[0];

An array of zero elements? A careless typo? How would read in a string with more than one character into this array? I think you meant to declare an array of size 10? Change that to 11 to accomodate the '\0' character and you should get AC. Remove your code after you get AC.

[Jemerson]

Thanx a lot for the help. The 0 size array is because i'm a java programmer and in java we can do this kinda thing. =] See you.

[qwerfv]

hi,everyone:

I can't find what's wrong in this code
please help with the code
any help would be appreciated..

Code: Select all

#include <iostream.h>
#include <algorithm>
#include <string>
void main()
{
        string s;
        int m,i;
        cin>>m;
        cin.get();

        for(i=0;i<m;i++){
                getline(cin,s);
                sort(s.begin(),s.end()-1);
                do
                {
                        cout<<s<<endl;

                }while(next_permutation(s.begin(),s.end()-1));
                cout<<endl;
        }
}

[tywok]

I don

[qwerfv]

Code: Select all

cin>>m;
cin.get();

can be replaced with
scanf("%d\n",&m); in c

and I use your code sort(s.begin(),s.end()) would output incorrectly in BCB5
I use my code can output correctly ...But I dont know why get WA(not TLE)..

[chunyi81]

That is the reason for the wrong answer. Please follow tywok's advice and you should get AC. UVA uses a different compiler than the one you used.