## 10098 - Generating Fast

Moderator: Board moderators

ancaacm
New poster
Posts: 7
Joined: Mon Oct 25, 2004 3:48 pm

ancaacm
New poster
Posts: 7
Joined: Mon Oct 25, 2004 3:48 pm

### 10098

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
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

### Generation optimisation

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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm
or if you use C++, you can be a lazy programer with the help of STL functions sort and next_permutation.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

### 10098 - Output limit I don't know why

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
for i:=1 to n do
begin
dl:=length(t);
if dl>10 then
halt;
lp:=0;
sortuj;
rob;
wyswietl;
end;
end.

NOthing special

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
Input:

Code: Select all

``````1
aaa
``````

Code: Select all

``````aaa
aaa
aaa
aaa
aaa
aaa
``````
Correct Output:

Code: Select all

``````aaa
``````
Two identical permutations muss not be printed...

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

### 10098 - next_permutation implementation help

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

Code: Select all

``````CUT AFTER ACC.
}``````
Last edited by Jemerson on Tue Jul 19, 2005 6:10 pm, edited 1 time in total.
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
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.
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

qwerfv
New poster
Posts: 3
Joined: Sat Nov 05, 2005 6:44 pm
Location: Taiwan

### 10098 WA help(c++)

hi,everyone:

I can't find what's wrong in this 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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am
I don
Impossible is nothing

qwerfv
New poster
Posts: 3
Joined: Sat Nov 05, 2005 6:44 pm
Location: Taiwan

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
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.