## 10098 - Generating Fast

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
From the problem description:
The maximum length of the string is 10.
So 'sleepchild' is a valid inputstring!

Think about the result of swap('sleepchild',3,4).

ray
New poster
Posts: 4
Joined: Mon Jun 02, 2003 1:04 pm

### 10098 why runtime error?

i used tree to solve this permutation. here is my source code in c :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct node{
char z;
};
void urut(char a[][11], int n);
void main()
{
int n, i,p,j,k;
char (*a)[11],b[50];
do{ scanf("%d",&n); fflush(stdin); }while(isalpha(n)||n<=0);
a=malloc(n*11);
for(i=0; i<n; i++)
{
scanf("%[^\n]",b); fflush(stdin);
p=strlen(b); k=0;
for(j=0; j<p; j++)
{
if( (b[j]>=65 && b[j]<=90) || (b[j]>=97 && b[j]<=122) )
a[k++]=b[j];
if(k==10) break;
} a[k]=NULL;
}
urut(a,n);
for(i=0; i<n; i++)
{
h=buat_awal(a);
s=h; rekursif(h,s);
printf("\n");
}
}
void urut(char a[][11], int n)
{
int i, j, k, p;
char t;
for(i=0;i<n; i++)
{
p=strlen(a);
for(j=1; j<p; j++)
{
t=a[j];
for(k=j; k>0; k--)
{
if(t<a[k-1]) a[k]=a[k-1];
else break;
}
a[k]=t;
}
}
}
{
int i, j;
i=strlen(k);
for(j=0; j<i; j++)
{
c->z=k[j]; c->next=0; c->par=0; c->des=0;
if(j==0) h=t=c;
else{ if(c->z!=t->z) t->next=c; t=c; }
}
return h;
}
{
link c, f, h1, t, r;
int b,count;
t=s;
while(h)
{
c=t; h1=h; b=0,count=0;
while(c)
{
if(c!=h)
{
r->z=c->z; r->next=0; r->par=h; r->des=0;
if(b==0) { s=f=r; h->des=r; }
else { f->next=r; f=r; }
b=1; count++;
}
c=c->next;
}
if(count>0)
{
h=h->des; rekursif(h,s);
}
h=h1; h=h->next;
}
if(count==0)cetak(s);
hapus(t);
}
{
char tem[15];
int d=0,i;
while(s)
{
tem[d++]=s->z;
s=s->par;
}
tem[d]=NULL;
for(i=d-1; i>=0; i--) printf("%c",tem);
printf("\n");
}
{
while(t)
{
v=t; t=t->next; v->next=0; free(v);
}
}

some one help me... [/c]

ray
New poster
Posts: 4
Joined: Mon Jun 02, 2003 1:04 pm

### 10098 why WA?? pls help me out of this...

i've repair my coding earlier where it was runtime error.
now i'm facing with WA. i'm sure my output is not wrong. you can try my output with my c source code :

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct node{
char z;
};
void urut(char a[][10], int n);
void main()
{
int n, i,p,j,k;
char (*a)[10];
do{ scanf("%d",&n); fflush(stdin); }while(isalpha(n)||n<=0);
a=malloc(n*11);
for(i=0; i<n; i++)
{
scanf("%s",a); fflush(stdin);
}
urut(a,n);
for(i=0; i<n; i++)
{
h=buat_awal(a);
s=h; rekursif(h,s);
printf("\n");
}
}
void urut(char a[][10], int n)
{
int i, j, k, p;
char t;
for(i=0;i<n; i++)
{
p=strlen(a);
for(j=1; j<p; j++)
{
t=a[j];
for(k=j; k>0; k--)
{
if(t<a[k-1]) a[k]=a[k-1];
else break;
}
a[k]=t;
}
}
}
{
int i, j;
i=strlen(k);
for(j=0; j<i; j++)
{
c->z=k[j]; c->next=0; c->par=0; c->des=0;
if(j==0) h=t=c;
else{ if(c->z!=t->z) t->next=c; t=c; }
}
return h;
}
{
link c, f, h1, t, r;
int b,count;
t=s;
while(h)
{
c=t; h1=h; b=0,count=0;
while(c)
{
if(c!=h)
{
r->z=c->z; r->next=0; r->par=h; r->des=0;
if(b==0) { s=f=r; h->des=r; }
else { f->next=r; f=r; }
b=1; count++;
}
c=c->next;
}
if(count>0)
{
h=h->des; rekursif(h,s);
}
h=h1; h=h->next;
}
if(count==0)cetak(s);
hapus(t);
}
{
char tem[11];
int d=0,i;
while(s)
{
tem[d++]=s->z;
s=s->par;
}
tem[d]=NULL; printf("\n");
for(i=d-1; i>=0; i--) printf("%c",tem);
}
{
while(t)
{
v=t; t=t->next; v->next=0; free(v);
}
}

pls someone tell me where is my fault?

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
hi. try with this input:

Code: Select all

``````1
aabcd``````
hope this helps.

ray
New poster
Posts: 4
Joined: Mon Jun 02, 2003 1:04 pm
thx for the help. i've fixed it like this in prototype link buat_awal
else{ if(c->z!=t->z) { t->next=c; t=c; } }
i hope you can find my fault. BTW thanks adil

ray
New poster
Posts: 4
Joined: Mon Jun 02, 2003 1:04 pm
i've fixed some of my coding
would you like to run again my source code and tell me why it is WA...

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct node
{
char z;
};
void urut(char a[][10], int n);
void main()
{
int n, i,p,j,k;
char (*a)[10];
do{ scanf("%d",&n); fflush(stdin); }while(isalpha(n)||n<=0);
a=malloc(n*11);
for(i=0; i<n; i++)
{
scanf("%s",a); fflush(stdin);
}
urut(a,n);
for(i=0; i<n; i++)
{
h=buat_awal(a);
s=h; rekursif(h,s);
if(i!=n-1)printf("\n");
}
}
void urut(char a[][10], int n)
{
int i, j, k, p;
char t;
for(i=0;i<n; i++)
{
p=strlen(a);
for(j=1; j<p; j++)
{
t=a[j];
for(k=j; k>0; k--)
{
if(t<a[k-1]) a[k]=a[k-1];
else break;
}
a[k]=t;
}
}
}
{
int i, j;
i=strlen(k);
for(j=0; j<i; j++)
{
c->z=k[j]; c->next=0; c->par=0; c->des=0;
if(j==0) h=t=c;
else { t->next=c; t=c; }
}
return h;
}
{
link c, f, h1, t, r;
int b,count;
t=s;
while(h)
{
if(h1->z==h->z) { h1=h; h=h->next; continue; }
c=t; h1=h; b=0,count=0;
while(c)
{
if(c!=h)
{
r->z=c->z; r->next=0; r->par=h; r->des=0;
if(b==0) { s=f=r; h->des=r; }
else { f->next=r; f=r; }
b=1; count++;
}
c=c->next;
}
if(count>0)
{
h=h->des; rekursif(h,s);
}
h=h1; h=h->next;
}
if(count==0)cetak(s);
hapus(t);
}
{
char tem[11];
int d=0,i;
while(s)
{
tem[d++]=s->z;
s=s->par;
}
tem[d]=NULL;
for(i=d-1; i>=0; i--) printf("%c",tem); printf("\n");
}
{
while(t)
{
v=t; t=t->next; v->next=0; free(v);
}
}

if input aab, is this the output should be?
aab
aba
baa

pls reply me ... i'm waiting for the good news

dserrano
New poster
Posts: 7
Joined: Tue Sep 17, 2002 2:39 am
kmhasan wrote:Try the following input:

Code: Select all

``````1
aaaaaaaaaaaaaa
``````
I believe that the output should be one line, your program will probably produce factorial(14) lines of output.
with that input, output should be:

Code: Select all

``a``

or

Code: Select all

``aaaaaaaaaaaaaa``
(only once)?

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
aaaaaaaaaaaaaa ( only once ).

Because when you do permutation again you will get the same answer again, and for output you must print the combination only once not more.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

I can't understand why this code is rejected (WA). Can anyone help me find what the problem is (if any)? Can anyone supply tricky input cases?
Thanks.

Code: Select all

``````(removed)
``````
Last edited by david on Fri Aug 13, 2004 12:36 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### short cut

There is a simpler approach for this problem.

You can use the function next_permutaion() to solve this problem.
And the function is under the h.f <algorithm>.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
I know I could use the STL, but the problem explicitly asks you for an algorithm to enumerate all permutations, not just use someone else's algorithm, which would render the problem trivial.
My approach to find the next permutation (sigperm function) consists of finding the maximum decreasing sequence ending at the end of a permutation (the sequence is v[i + 1..tamano)), next exchanging v with the smallest element in v[i + 1..tamano) larger than v, and finally reversing v[i + 1..tamano). (The function sigperm returns 0 if the permutation given was the last one in lexicographic order).
The algorithm is correct, and I cannot find any flaws in my implementation, nor test cases for which my program fails.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### OOOOOpsi

Your algorithm seems to be correct but the implementation seems to be a little off the track.

Here is a case that gives incorrect output with your code.

input
[c]
1
aabb
[/c]

[c]
aabb
abba
baba
bbaa
[/c]

I hope you can see the mistake. There should be 6 permutations.
I know I could use the STL, but the problem explicitly asks you for an algorithm to enumerate all permutations, not just use someone else's algorithm, which would render the problem trivial.
Thats very good. You don't like using other people's algorithm.
OOOps... You have used qsort, but I don't see any pivoting/partitioning. Which means its built in.... just kidding.

In real time contests where time is very crucial the usage of built in functions can be very handy. But in 24s I appreciate your steps.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Many thanks for that. I found my mistake --fixing it amounted to writing a <= in place of a <.
As for quicksort... you're right, but then again using it merely helps you with an unimportant part of the problem (as opposed to directly solving it)
Of course in a contest I wouldn't hesitate to use next_perm and all that, but one doesn't get much practice by writing a 10-line program and submitting it to the UVA judge.. And to be honest I haven't used the STL much so far, though I think it could indeed come in handy in contest situations (for instance, I don't believe anyone could afford to code his own heap or balanced-tree routines unless he is prepared to spend the best part of the contest time on a single problem..)

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

### Runtime Error(SIGSEGV)????

it's about 10098 problem, and every time I submit it gives me that error.
What does it means?. About 10 minutes ago gaved me Time limit exceeded, and now it gives me this, that I understood, but this....., and I;m afraid that I deleted the judje-uva sender from my email.....

pleeease help...
thanks, Anca

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Runtime Error(SIGSEGV)

This error means that the program crashed due to segmentation fault. It usually happens if your code tries to access elements beyond an array.

for example,

int a[10];

in your code if you use the statement a[1000], this run time error will occur.