10098 - Generating Fast

[little joey]

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]

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>
typedef struct node *link;
struct node{
char z;
link next, par, des;
};
void urut(char a[][11], int n);
link buat_awal(char k[]);
void rekursif(link h, link s);
void cetak(link h1);
void hapus(link t);
void main()
{
link h,s;
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;
}
}
}
link buat_awal(char k[])
{
link t,c,h;
int i, j;
i=strlen(k);
for(j=0; j<i; j++)
{
c=(link)malloc(sizeof(struct node));
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;
}
void rekursif(link h, link s)
{
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=(link)malloc(sizeof(struct node));
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);
}
void cetak(link s)
{
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");
}
void hapus(link t)
{
link v;
while(t)
{
v=t; t=t->next; v->next=0; free(v);
}
}

some one help me... [/c]

[ray]

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>
typedef struct node *link;
struct node{
char z;
link next, par, des;
};
void urut(char a[][10], int n);
link buat_awal(char k[]);
void rekursif(link h, link s);
void cetak(link h1);
void hapus(link t);
void main()
{
link h,s;
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;
}
}
}
link buat_awal(char k[])
{
link t,c,h;
int i, j;
i=strlen(k);
for(j=0; j<i; j++)
{
c=(link)malloc(sizeof(struct node));
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;
}
void rekursif(link h, link s)
{
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=(link)malloc(sizeof(struct node));
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);
}
void cetak(link s)
{
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);
}
void hapus(link t)
{
link v;
while(t)
{
v=t; t=t->next; v->next=0; free(v);
}
}

pls someone tell me where is my fault?

[Adil]

hi. try with this input:

Code: Select all

1
aabcd

hope this helps.

[ray]

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; } }
it answered aabcd like abcd. But it's still wrong answer
i hope you can find my fault. BTW thanks adil

[ray]

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>
typedef struct node *link;
struct node
{
char z;
link next, par, des;
};
void urut(char a[][10], int n);
link buat_awal(char k[]);
void rekursif(link h, link s);
void cetak(link h1);
void hapus(link t);
void main()
{
link h,s;
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;
}
}
}
link buat_awal(char k[])
{
link t,c,h;
int i, j;
i=strlen(k);
for(j=0; j<i; j++)
{
c=(link)malloc(sizeof(struct node));
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;
}
void rekursif(link h, link s)
{
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=(link)malloc(sizeof(struct node));
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);
}
void cetak(link s)
{
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");
}
void hapus(link t)
{
link v;
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]

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]

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]

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)

[sohel]

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]

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]

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]

Your code outputs
[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]

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]

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]

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.