Page 1 of 5

P200 : What's wrong with my program ?

Posted: Wed May 08, 2002 6:27 am
by Shiori
#include<iostream.h>
#include<string.h>

void main()
{
char c[30], d[30], w[27], *c1, *d1;
int g[26][26], v[26], p[26], q[26], qh, qt, s1, s2, n;
for (; 1;)
{
cin >> c;
if (cin.fail()) break;
memset(g, 0, sizeof(g));
memset(v, 0xFF, sizeof(v));
memset(p, 0, sizeof(p));
n = 0;
if (*c == '#')
{
cout << endl;
continue;
}
for (cin >> d; *d != '#'; cin >> d)
{
for (c1 = c, d1 = d; *c1 && *d1 && *c1 == *d1; c1++, d1++);
if (*c1 && *d1)
{
if (v[*c1 - 'A'] == -1)
w[s1 = v[*c1 - 'A'] = n++] = *c1;
else
s1 = v[*c1 - 'A'];
if (v[*d1 - 'A'] == -1)
w[s2 = v[*d1 - 'A'] = n++] = *d1;
else
s2 = v[*d1 - 'A'];
g[s1][s2] = 1;
p[s2]++;
strcpy(c, d);
}
else if (!(*c1)) strcpy(c, d);
}
for (s2 = 0; p[s2]; s2++);
q[0] = s2;
for (qh = qt = 0; qh <= qt; qh++)
{
s1 = q[qh];
cout << w[s1];
for (s2 = 0; s2 < n; s2++)
if (g[s1][s2])
{
p[s2]--;
if (!p[s2]) q[++qt] = s2;
}
}
cout << endl;
}
}

200

Posted: Tue Jul 16, 2002 6:08 pm
by htl
It always get RE. But I don't know what's wrong with my program. Could someone help me? I think the code isn't hard for you read.
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define YES 1
#define NO 0
void main(void)
{
int len1,len2,len,x,cost[26][26],in[26],y,stack[26],top,v[26];
char s1[20],s2[20],c1,c2;
for(x=0;x<26;x++)
v[x]=NO,in[x]=0;
for(x=0;x<26;x++)
for(y=0;y<26;y++)
cost[x][y]=NO;
scanf("%s",s1);
if(strcmp(s1,"#")==0)
exit(0);
while(1)
{
scanf("%s",s2);
if(strcmp(s2,"#")==0)
break;
len1=strlen(s1);
len2=strlen(s2);
if(len1<len2)
len=len1;
else
len=len2;
for(x=0;x<len;x++)
if(s1[x]!=s2[x])
break;
if(x==len)
{
strcpy(s1,s2);
continue;
}
c1=s1[x],c2=s2[x];
v[c1-'A']=v[c2-'A']=YES;
cost[c1-'A'][c2-'A']=YES;
in[c2-'A']++;
strcpy(s1,s2);
}
for(x=0,top=-1;x<26;x++)
if(v[x] && !in[x])
stack[++top]=x;
while(1)
{
if(top==-1)
break;
x=stack[top--];
for(y=0;y<26;y++)
if(v[y] && cost[x][y])
{
cost[x][y]=NO;
in[y]--;
if(in[y]==0)
stack[++top]=y;
}
printf("%c",'A'+x);
}
printf("\n");
}
[/c]

Posted: Mon Jul 22, 2002 5:31 pm
by htl
Could someone help me? I want to know if my code of topology sort algo is correct.

Problem 200 - Runtime error(SIGSEGV)

Posted: Tue Aug 06, 2002 10:05 am
by Madouka
What's runtime error mean? I think I had done it right.
Sample input
xxyy
yywz
zzw
#

/*output */
xywz
Please explain to me, what should i do?

Posted: Wed Oct 09, 2002 4:21 am
by pendryko
xwy
xty
Bus error(core dumped)

i can't finish my input, because your prog is dumped.

Re: Problem 200 - Runtime error(SIGSEGV)

Posted: Wed Oct 30, 2002 8:49 am
by supermin
[quote="Madouka"]What's runtime error mean? I think I had done it right.
Sample input
xxyy
yywz
zzw
#

/*output */
xywz
Please explain to me, what should i do?[/quote]

I think the right is xyz,not xywz as you said...

Posted: Wed Oct 30, 2002 4:07 pm
by cytse
Well...I don't think the input data provided by Madouka is valid, because it does not provide enough information for a complete ordering.

Posted: Wed Oct 30, 2002 5:09 pm
by supermin
[quote="cytse"]Well...I don't think the input data provided by Madouka is valid, because it does not provide enough information for a complete ordering.[/quote]

hmm..this is my carelessness...
the problem said :

"Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used. "

Posted: Thu Jan 30, 2003 9:44 am
by epsilon0
i just solved this problem this morning. it's easy.

take it easy and use functions. don't write everything in the main(). this is unreadable, and people can't help you.

my basic algo is:

if letter X goes before letter Y, matrix[x][Y] = 1
you then have a graph, and wish to find the longer path in it.
find the first element. easy: the first element has no ancestor in the graph.
then call a recursive function to find the successor of the first element.
i call order[X] the length of the longest path starting from X.
notice that if Yi are successors of X then order[X] = max(order[Yi]) + 1.
the successor of X is then the Yi that has the biggest order.
when this is done, just follow the list of successors from the first letter (order = N if there are N letters) to the last one (order = 0).

example:

XYZ
XZ
ZY
ZX
#

line 1 and 2 give you: Y goes before Z
line 2 and 3 give you: X goes before Z
line 3 and 4 give you: Y goes before X

the matrix is then:
+XYZ
X001
Y101
Z000

notice that Y has no successor (row of 0's), it is the first element.
then Y has two successors X and Z, find their order.
+X has one successor Z, find its order.
++Z has no successor, its order is 1
+the order of X is then 1+1 = 2 and its successor is Z
+order of Z already computed, 0.
thus order of Y = max(1,0) + 1 = 2, and its successor is X.

the order is then Y -> X -> Z

hope this is clear, good luck

200 Problem

Posted: Thu Apr 10, 2003 9:13 pm
by Eva
Hi!
I am new not only in programming but also in online contests.

here I was trying to solve 200.

I have solved few problems related with lexographic comparisons.
But this seems inverse of that?

I am not getting any clue. Help please :oops:

Posted: Thu Apr 10, 2003 11:37 pm
by turuthok
Hello, I it is indeed a lexicographical comparison.

Long time ago, I solved this with crude logic that I can't even remember today. However, I then studied Topological Sort and solved it again using that algo.

Code: Select all

XWY
ZX
ZXY
ZXW
YWWX
From Line 1 and Line 2, we know X < Z.
From Line 2 and Line 3, we can't get any additional info.
From Line 3 and Line 4, we know Y < W.
From Line 4 and Line 5, we know Z < Y.

Based on 3 relations above, we know the output should be X < Z < Y < W.

-turuthok-

200 Rare Order [Topological Sort]

Posted: Sat Jul 26, 2003 6:52 am
by hank
I got WA,and I still cannot find any wrong in my code.
please help me! Thanks!!

[c]#include "stdio.h"
#include "string.h"
int mark[26],map[26][26],degree[26];
void main()
{
char arr[27],lastarr[27];
int i,j,k,n,len1,len2,len;
memset(mark,0,sizeof(mark));
memset(map,0,sizeof(map));
memset(degree,0,sizeof(degree));
n=0;
while( gets(arr) ){
if(!strlen(arr)) continue;
if(arr[0]=='#') break;
if(n){
len1=strlen(lastarr);
len2=strlen(arr);
for(i=0;i<len1;i++) mark[lastarr-'A']=1;
for(i=0;i<len2;i++) mark[arr-'A']=1;
len=len1<len2?len1:len2;
for(i=0;i<len;i++)
if(lastarr!=arr&&map[lastarr-'A'][arr-'A']==0){
degree[arr-'A']++;
map[lastarr-'A'][arr-'A']=1;
break;
}
}
n++;
strcpy(lastarr,arr);
}
do{
k=1;
for(i=0;i<26;i++){
if(degree==0&&mark[i]==1){
mark[i]=0;
for(j=0;j<26;j++)
if(map[i][j] && degree[j]>0)
degree[j]--;
printf("%c",i+'A');
k=0;
break;
}
}
}while(!k);
}[/c]

my method is:

Code: Select all

topological sort

200(Run Time Error)

Posted: Fri Aug 08, 2003 6:12 am
by samueljj
Here is my coding for problem 200(Rare Order). I know it seems way too big for some of you but still I dont think it should get RTE. Can anybode tell
me where is the problem?
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define SMAX 60

/* global declaration */
char ordlist[MAX];
char str[MAX][SMAX];
int l=0,num=0;
int StringCompare(char *str1,char *str2);
void replace(char c1, char c2);

int main()
{
char tmp[SMAX];
int i=0,ind=0;
while(gets(tmp)!=NULL)
{
if(!strcmp(tmp,"#")) break;
strcpy(str,tmp);
num++;
i++;
}
for(i=1;i<num;i++)
{
ind=StringCompare(str[i-1],str);
if(ind<0) continue;
replace(str[i-1][ind],str[ind]);
}
ordlist[l]='\0';
l=0;
printf("%s",ordlist);
return 0;
}

int StringCompare(char *str1, char *str2)/*finds the first unmatch index between str1 and str2*/
{
int i=0;
char *tmp1,*tmp2;
if(strlen(str1)>=strlen(str2))
{strcpy(tmp1,str1); strcpy(tmp2,str2);}
else
{strcpy(tmp1,str2);strcpy(tmp2,str1);}
for(i=0;i<strlen(tmp1);i++)
if(i<strlen(tmp2))
{
if(tmp1!=tmp2)
return i;
}
else
return -1;
return -1;
}

void replace(char c1,char c2)/*places c1 and c2 in ordlist according to the order c1, c2*/
{
int i,keep,ind1=-1,ind2=-1;
char tmp;
for(i=0;i<l;i++)/* finds the position of c1 in ordlist*/
if(ordlist==c1)
{
ind1=i; break;
}
for(i=0;i<l;i++)/* finds the position of c2 in ordlist*/
if(ordlist==c2)
{
ind2=i; break;
}
if(ind1<0 && ind2<0)/*when c1 and c2 both are not found in ordlist*/
{
ordlist[l]=c1;
ordlist[l+1]=c2;
l+=2;
return;
}
else if(ind1<0)/*when c1 not found in ordlist*/
{
for(i=(l-1);i>=ind2;i--)
ordlist[i+1]=ordlist;
ordlist[ind2]=c1;
l++;
}
else if(ind2<0)/*when c2 not found in ordlist*/
{
ordlist[l]=c2;
l++;
}
else
{
if(ind1>ind2)/*when both are found */
{
tmp=ordlist[ind2];
for(i=ind2+1;i<=ind1;i++)
ordlist[i-1]=ordlist;
ordlist[ind1]=tmp;
}
}
}[/c]

Posted: Fri Aug 08, 2003 6:20 am
by UFP2161
Your problem code lies in stringCompare() within the following lines:
[c]char *tmp1,*tmp2;
if(strlen(str1)>=strlen(str2))
{strcpy(tmp1,str1); strcpy(tmp2,str2);}
else
{strcpy(tmp1,str2);strcpy(tmp2,str1);}[/c]
The rest is up to you to figure out =)

Posted: Sat Aug 09, 2003 6:09 am
by samueljj
Thanks! I got ACC now :D