511 - Do You Know the Way to San Jose? - Do nothing AC

[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;
}
}

[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]

[htl]

Could someone help me? I want to know if my code of topology sort algo is correct.

[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?

[pendryko]

xwy
xty
Bus error(core dumped)

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

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

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

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

[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

[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

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

[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

[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]

[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 =)

[samueljj]

Thanks! I got ACC now