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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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). :wink:

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

10098 why runtime error?

Post by 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... :cry: [/c]

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

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

Post by 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
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

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

Post by 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 :cry:
i hope you can find my fault. BTW thanks adil

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

Post by ray »

i've fixed some of my coding
would you like to run again my source code and tell me why it is WA... :cry:

#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 :oops:

dserrano
New poster
Posts: 7
Joined: Tue Sep 17, 2002 2:39 am

Post by dserrano »

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

Post by 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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

10098, wrong answer

Post by 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)
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

Post by 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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by 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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

OOOOOpsi

Post by 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. :x

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. :roll:
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. :P You don't like using other people's algorithm.
OOOps... :o 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. 8)

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

Post by david »

Many thanks for that. I found my mistake --fixing it amounted to writing a <= in place of a <.
As for quicksort... :D 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)????

Post by 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... :cry:
thanks, Anca

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

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

Post Reply

Return to “Volume 100 (10000-10099)”