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

[stcheung]

Well I have read all related posts for this problem so I pretty much know what I have to do: first store the partial ordering into a 2-dimensional array called before[][] and then run topological sort on it. Below is my code and I keep getting TLE and I don't think it's because of infinite loop. I don't think my code is really THAT slow either. Can someone test my code against some sample input to see whether it really encounters an infinite loop? Thanks in advance for any help provided.

[cpp]/* 200 */
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>

int degree[26];
bool before[26][26];
int array[26];
int arraysize=0;

bool lessthan(const int, const int);

int main()
{
int size=0;
string lines[100000];
int length[100000];
bool exist[26];
for(int i=0; i<26; i++)
{
for(int j=0; j<26; j++)
{
before[j] = false;
}
exist = false;
}

string s;
while(true)
{
cin >> s;
if(s == "#")
break;
lines[size] = s;
length[size] = s.length();
for(int i=0; i<length[size]; i++)
exist[s - 'A'] = true;
size++;
}

int numcomp = 0;
string a,b;
while(true)
{
bool changed = false;
for(int i=0; i<size-1; i++)
{
for(int j=i+1; j<size; j++)
{
a = lines.substr(0, numcomp);
b = lines[j].substr(0, numcomp);
if(a == b)
{
changed = true;
if(length > numcomp && length[j] > numcomp
&& lines[numcomp] != lines[j][numcomp])
{
int m = lines[numcomp] - 'A';
int n = lines[j][numcomp] - 'A';
before[m][n] = true;
}
}
}
}

numcomp++;
if(!changed)
break;
}

for(int i=0; i<26; i++)
{
if(exist)
{
array[arraysize] = i;
arraysize++;
}
}

int current=0;
string result="";

for(int i=current; i<arraysize; i++)
degree = 0;
for(int i=0; i<arraysize; i++)
{
for(int j=0; j<arraysize; j++)
{
if(before[array][array[j]])
degree[i]++;
}
}



int next;
while(true)
{
for(int i=0; i<arraysize; i++)
{
if(degree[i] == 0)
{
next = i;
degree[i] = -1;
current++;
break;
}
}

for(int k=0; k<arraysize; k++)
{
if(before[array[k]][array[next]])
{
degree[k]--;
before[array[k]][array[next]] = false;
}
}
result = (char)(array[next] + 'A') + result;
if(current >= arraysize)
break;
}

cout << result;
return 0;
}

bool lessthan(const int a, const int b)
{
degree[a] < degree;
}[/cpp]

[Subeen]

I got WA in this problem. I used topological sort here. please test my program to find the bug. Here is the code:
[c]#include <stdio.h>
#include <string.h>

void main()
{
int g[30][30];
int indegree[30];
int qara[1000], head, tail, sorted[30], taken[30];

char in[30], pre[30];

int i, j, u, flag=1, l, l1, l2;

while(flag)
{
flag = 0;
pre[0] = 0;
memset(g, 0, sizeof(g));
memset(taken, 0, sizeof(taken));
for(i=0; i<30; i++) indegree = -1;
head = tail = 0;
while(1==scanf("%s", in) && in[0]!='#')
{
if(!flag) flag = 1;
if(pre[0])
{
l1 = strlen(in);
l2 = strlen(pre);
(l1 < l2) ? l = l1 : l = l2;

for(i=0; i<l; i++)
{
if(pre != in)
{
g[pre-'A'][in-'A'] = 1;
if(indegree[pre-'A']==-1) indegree[pre-'A'] = 0;
if(indegree[in-'A']==-1) indegree[in-'A'] = 1;
else indegree[in-'A']++;
break;
}
}
}
strcpy(pre, in);
}
if(!flag) break;
for(i=0; i<30; i++)
if(!indegree[i])
qara[tail++] = i;

i = 0;
while(head!=tail && i<30)
{
u = qara[head++];
sorted[i++] = u;
taken = 1;

for(j=0; j<30; j++)
{
if(g[j] && !taken[j])
{
indegree[j]--;
if(!indegree[j])
qara[tail++] = j;
}
}
}


for(j=0; j<i; j++)
printf("%c", (char)(sorted[j]+'A'));

printf("\n");

}
}[/c]

thank you.

[GreenPenInc]

I got TLE, then I changed a line and got AC. One nice thing is that you can assume consistency in ordering, so if you check your matrix and find that you already know the relation between i and j, there's no need to check it against the computed one. This lets you prune, or at least it let me prune. I used recursion to fill my matrix.

[abishek]

i feel that this problem does not have a testcase which tests the extreme when the input is

AAAAAAA
#
for which the output i feel must be
A

as this is not output by my AC program when I checked it again, i feel that the judge must include
such input also
bye
abi

[ConaN]

This problem is very easy if you use a 2d matrix (zero one).and check transitivity , , a<m && m<c => a<c is similar to 124 "Following Orders" , but easier because you not have to create all the posibilities

[Minilek]

I have submitted this problem also, but got WA. Is there something I'm doing improperly ?? I keep checking the last string with the current one and break and update my relation matrix whenever I find a character that is different among the 2. At the end I update the relation matrix to include transitive relations then sort and display. So far my code has passed all my examples, but is there something I'm missing?

Thanks.

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int rel[26][26];

int seqcmp(const void *va, const void *vb) {
char c = *(char *)va, d = *(char *)vb;
return rel[c-'A'][d-'A'];
}


int main() {
char tosort[26],last[21],cur[21];
int i,j,k,l,m,n,appear[26];
for (i=0;i<26;i++) appear = 0;
for (i=0;i<26;i++) for (j=0;j<26;j++) rel[j] = 0;
scanf("%s",last);
if (last[0]=='#') { printf("\n"); exit(0); }
for (i=0;i<strlen(last);i++) appear[last-'A'] = 1;
while (1) {
scanf("%s",cur);
if (cur[0]=='#') break;
m = strlen(cur);
n = strlen(last);
for (i=0;i<(m<n)?m:n;i++) {
if (cur==last) continue;
rel[last-'A'][cur-'A'] = -1;
rel[cur-'A'][last-'A'] = 1;
break;
}
strcpy(last,cur);
for (i=0;i<m;i++) appear[last-'A'] = 1;
}
for (i=0;i<26;i++) {
for (j=0;j<26;j++) {
if (!appear[j]) continue;
for (k=0;k<26;k++) {
if (!appear[k]) continue;
for (l=0;l<26;l++) {
if (!appear[l]) continue;
if (rel[j][k]==-1 && rel[k][l]==-1) {
rel[l][j] = 1; rel[j][l] = -1;
}
else if (rel[j][k]==1 && rel[k][l]==1) {
rel[l][j] = -1; rel[j][l] = 1;
}
}
}
}
}
i = 0;
for (j=0;j<26;j++) if (appear[j]) tosort[i++] = j + 'A';
qsort(tosort,i,sizeof(char),seqcmp);
for (j=0;j<i;j++) printf("%c",tosort[j]);
printf("\n");
exit(0);
}
[/c]

[Minilek]

I changed my code above and got AC. In particular,
I took out the following code and put in a recursive function
instead:

[c]
for (i=0;i<26;i++) {
for (j=0;j<26;j++) {
if (!appear[j]) continue;
for (k=0;k<26;k++) {
if (!appear[k]) continue;
for (l=0;l<26;l++) {
if (!appear[l]) continue;
if (rel[j][k]==-1 && rel[k][l]==-1) {
rel[l][j] = 1; rel[j][l] = -1;
}
else if (rel[j][k]==1 && rel[k][l]==1) {
rel[l][j] = -1; rel[j][l] = 1;
}
}
}
}
}
[/c]

I still don't understand though why the above code is incorrect.
Does anyone see? My reasoning was that since there cannot be
more than 26 letters used, transitive chains cannot be more than
25 links long (but I did ..;i<26;..) just in case. I even tried changing
this to loop to i<100 but that still got WA. Is there something tricky
I'm missing here? Thanks.

[rimu]

i'm really confused with the problem description,
could someone please tell me is the following
set of input valid? if not why?

BC
CA
CB
#

my commonsense tell me the ordering should be
ABC but accepted code for this problem ( one of
my friend's ) gives output BCA !!!!!!!

why is this happening?

[mohiul alam prince]

Hi
for this input the output will BCA.
because you have given a dictionary and it is sorted u have find out a
way that will be give u the write answer.

I have solve this problem by this way
- First i have taken a Array
- Then i have stored one by one
- If one alphabet is come first then I have maked it that the next time
i will never take this.

Exp
BC
CA
CB
#
For this input I have search collom wise which one is first
then
A[0] = 'B' and i have visited 'B'
next time came 'C'
then
A[1] = 'C' and i have visited it
then nest time again came 'C'
but I will never enter this
next time i have search the next collom.
after finished the search i have printed this A[] array
this is my way hope u will understand.

thanks:)
MAP

[mf]

My AC program gives the answer "ABC". But I solved the problem algebraically (relations, transitivity etc).

[mohiul alam prince]

"mf wrote"

My AC program gives the answer "ABC". But I solved the problem algebraically (relations, transitivity etc).

ru sure for this output. my AC programm gives "BCA".Can u say
which one is currect.

MAP

[mf]

Unfortunately, the judge's input for this problem is just one case. So if someone gets accepted, it only means that his/her program produced the desired output for that particular case.

I'm sure "ABC" is the correct answer for the input posted above. Here's my reasoning:

1. Since string "BC" precedes "CA", I have: 'B' < 'C'.

2. String "CA" precedes "CB". The first letters of both strings are equal,
so sorting lexicographically I'd have to order the strings by their second letters.
I conclude that 'A' < 'B'.

3. From steps 1 and 2, I have: 'B' < 'C', and 'A' < 'B'. Rearranging: 'A' < 'B' < 'C'. So my answer is "ABC".

[firec]

I solved 200 by detecting all the "less than" relations between the characters, storing these relations in a matrix. Then, I find the only character that is not in the right-hand-side in all the relations, output it, delete all its related relations and repeat until all characters are output.

I got the algorithm early, but spent a significant amount of time on a bug which I don't understand.

This was my original submission (important parts snipped), which got RE:

Code: Select all

...
int min(int a,int b){
        if(a<b)return a;
        return b;
}
int main(){
        char s[100],old[100];
        int c[26]={0};
        int a[26][26]={0};
        cin>>old;
        for(int i=0;i<strlen(old);i++) c[old[i]-'A'] = 1;
        while(cin>>s){
                if(s[0]=='#')break;
                int i=0;
                int l=min(strlen(s),strlen(old));
                while(i<l && s[i]==old[i]) i++; //<<-- problematic line!
                a[ old[i]-'A' ][ s[i]-'A' ] = 1;
...

This was my AC code, after a long painful process of "isolating" my error:

Code: Select all

...
int main() {
  char s[100],old[100];
  int c[26]={0};
  int a[26][26]={0};
  cin>>old;
  for(int i=0;i<strlen(old);i++) c[old[i]-'A'] = 1;
  while(cin>>s) {
    if(s[0]=='#')break;
    int i=0;
    if(strlen(s)<strlen(old)) {
      for(i=0;i<strlen(s);i++) if(s[i]!=old[i]) break;
      if(s[i]!='\0' && old[i]!='\0') a[ old[i]-'A' ][ s[i]-'A' ] = 1;
    } 
    else {
      for(i=0;i<strlen(old);i++) if(s[i]!=old[i]) break;
      if(s[i]!='\0' && old[i]!='\0') a[ old[i]-'A' ][ s[i]-'A' ] = 1;
    }

Notice the similarity in logic? I can't explain why my first code doesn't work. Appreciate some help in cracking this mystery.

[Jelly_Fish]

Hi all

can u please help with this problem .. its been 2 days i tried many ways to solve this problem but i always get RUN TIME ERROR i dont why it works fine with many test cases! ... can u plz test my code or just give any critical input to test .. i really dont know where is the problem

i tried the posted input ..
BC
CA
CB#

and it worked fine
ABC

/////////////////////////// my code /////////////////////////////
#include<iostream>
#include<string>
using namespace std;

main()
{
///////////////////////////////////////INPUT//////////////////////////////////////////
string s[1000];
char buffer[20];
int n=0;

while (1)
{
cin.getline(buffer,20);
if (buffer[0] == '#')
break;
s[n++]=buffer;
}
////////////////////////////////////////SOLUTION/////////////////////////////////////////////

int k,y,q; // counters
int num=0; // number of characters
bool flag=true;
char chars[26]; // max chars
int relations[26][26];


for(k=0; k<n; k++) // count characters
for(y=0; y<s[k].length(); y++)
{
flag = true;
for(q=0; q<num; q++)
if( s[k][y] == chars[q] )
flag = false;
if (flag == true)
chars[num++]=s[k][y];
}

for(k=0; k<num; k++) // initilize relations
for(y=0; y<num; y++)
relations[k][y]=0;

/////////////////////////////////////////////////////////////////////////////////////

int i,j;
int f,g;
for(j=0; j<20; j++) //find relations
{
for(i=0; i<n-1; i++)
{
if(j==0)
{
if(s[j] != s[i+1][j])
{
for(f=0;f<num;f++)
if(s[j]==chars[f])
break;
for(g=0;g<num;g++)
if(s[i+1][j]==chars[g])
break;
relations[g][f]=1; // mark relations
}
}
else if( (j<s.length()) && (j<s[i+1].length()) ) //
{
if(s[j-1] == s[i+1][j-1]) // previous column
{
if(s[j] != s[i+1][j]) // if not equal .. i>i+1
{
for(f=0;f<num;f++)
if(s[j]==chars[f])
break;
for(g=0;g<num;g++)
if(s[i+1][j]==chars[g])
break;
relations[g][f]=1; //
}
}
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////

i=j=0;
int b;
int x=0;
int order[26];

for(i=0; i<num; i++)
{
flag=true;
for(j=0; j<num; j++)
if(relations[j] != 0)
flag=false;

if(flag==true) // find index of the row which contains only 0s
{
order[x++]=i;
b=i;
break;
}
}

/////////////////

while(x!=num)
{
j=b;
for(i=0; i<num; i++)
if(relations[j] == 1) // j is always b
{
order[x++]=i;
b=i; // go the column i
break;
}
}

for(int a=0; a<num; a++)
cout << chars[order[a]];



return 0;
}

[Wei-Ming Chen]

Hi, I got Wa on 200. But I tried many inputs and outputs. They were all right.

Can some help?

Code: Select all

#include <stdio.h>
#include <string.h>
bool a[27][27],b[27];
int c[27];
int dfs(int u)
{
    int v,w,x;
    for(v=1;v<=26;v++)
    {
        if((a[u][v]==1 && b[v]==0) && c[v]==0)
        {
            b[v]=1;
            printf("%c",v+64);
            for(w=1;w<=26;w++)
            {
                if(a[v][w]==1)
                {
                    c[w]--;
                }
            }
            dfs(v);
        }
    }
}
int main()
{
    int e,f,g,h,s1,s2,u1,u2;
    bool i[27];
    char d1[30],d2[30];
    for(f=1;f<=26;f++)
    {
        for(g=1;g<=26;g++)
        {
            a[f][g]=0;
        }
        b[f]=0;
        c[f]=0;
        i[f]=0;
    }
    gets(d1);
    s1=strlen(d1);
    for(;;)
    {
        gets(d2);
        s2=strlen(d2);
        if(s2==1 && d2[0]=='#')
        {
            break;
        }
        for(e=0;e<s1,e<s2;e++)
        {
            if(d1[e]!=d2[e])
            {
                u1=d1[e]-64;
                u2=d2[e]-64;
                a[u1][u2]=1;
                i[u1]=1;
                i[u2]=1;
                break;
            }
        }
        for(e=0;e<s2;e++)
        {
            d1[e]=d2[e];
        }
        s1=s2;
    }
    for(f=1;f<=26;f++)
    {
        for(g=1;g<=26;g++)
        {
            if(a[f][g]==1)
            {
                c[g]++;
            }
        }
    }
    for(e=1;e<=26;e++)
    {
        if((c[e]==0 && b[e]==0) && i[e]!=0)
        {
            printf("%c",e+64);
            b[e]=1;
            for(f=1;f<=26;f++)
            {
                if(a[e][f]==1)
                {
                    c[f]--;
                }
            }
            dfs(e);
        }
    }
    printf("\n");getchar();
    return 0;
}