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

The forum to report every bug you find or tell us what you'd like to find in UVa OJ

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

200 Time Limit Exceeded

Post by 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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by 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
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by 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.
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

not enough test cases

Post by 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
New poster
Posts: 1
Joined: Sun Jan 04, 2004 3:26 am
Location: Venezuela
Contact:

rare order and discrete structures

Post by 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
--------------------------//---------------------------
_PrOgRaMaKeR_
if (you insist) {you'll beat}; // BeLiEvE!!!
:D

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by 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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by 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
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

HELP!!! 200 DON'T UNDERSTAND

Post by 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?
i'll be back

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by 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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

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

MAP

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
New poster
Posts: 1
Joined: Sat Mar 26, 2005 3:51 am

200 - I got AC but I'm still puzzled

Post by 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
New poster
Posts: 1
Joined: Sun Jun 26, 2005 11:07 pm

tired of problem 200 :(

Post by 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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

ACM 200 WA

Post by 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;
}

Locked

Return to “Bugs and suggestions”