10098 - Generating Fast

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

Moderator: Board moderators

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

Post by ancaacm » Tue Oct 26, 2004 11:24 pm

thanks, ya it was this. :oops: :D

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

10098

Post by ancaacm » Wed Oct 27, 2004 1:13 pm

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..... :wink: ?

thanks.

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

Generation optimisation

Post by Zuza » Wed Oct 27, 2004 2:30 pm

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

Post by eg_frx » Thu Oct 28, 2004 5:11 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

Post by Antonio Ocampo » Sun Nov 07, 2004 3:05 am

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 :P . Thanks in advance

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Nov 08, 2004 12:46 am

I found the mistake :wink: . 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

Post by qndel » Tue Jun 07, 2005 12:51 pm

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!!!!
NOthing special

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

Post by Zuza » Sun Jun 12, 2005 7:40 pm

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

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

10098 - next_permutation implementation help

Post by Jemerson » Wed Jul 06, 2005 12:21 am

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

Post by chunyi81 » Sun Jul 17, 2005 7:56 am

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.

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

Post by Jemerson » Tue Jul 19, 2005 6:15 pm

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++)

Post by qwerfv » Sat Nov 05, 2005 6:59 pm

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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sat Nov 05, 2005 7:17 pm

I don
Impossible is nothing

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

Post by qwerfv » Sun Nov 06, 2005 4:43 am

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

Post by chunyi81 » Sun Nov 06, 2005 9:55 am

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.

Post Reply

Return to “Volume 100 (10000-10099)”