175 - Keywords

[wyvmak]

question about input and output.

i think for "P: 3 concepts conceptions". "
T: Don't Rock --- the Boat as Metaphor in 1984, Concepts
and (Mis)-Conceptions of an Art Historian.| " should meet the profile. but the sample output just doesn't have it. why?

[Even]

The problem says that
"All non-alphabetic characters are to be ignored" and "HP2100X will be treated as HPX"

so the "(Mis)-Conceptions" will be treated as "MisConceptions"...

[monika]

Hi,

Could someone please help me identify why I'm getting RunTime Error:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.

My program is:
-------------
/* @JUDGE_ID: 21235WP 175 C "Recursion" */

/* @BEGIN_OF_SOURCE_CODE */


#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>


void main()
{
int search(int, char*, char*);

int pi=0, ti=0;
char *P[50], *T[250];
int threshold[50];
int i,j,k;

char c;
char str[85];

while( (c=getchar()) != '#')
{
if( c == 'P' )
{
scanf("%*c%d%[^\n]s", &threshold[pi],str);
P[pi] = malloc(strlen(str)+1);
strcpy(P[pi],str);
pi++;

threshold[pi] = abs(threshold[pi]);

}
else if (c == 'T' )
{
scanf("%*c%[^|]s", str);

for(i=0,k=0; k<strlen(str); k++)
{
c = toupper(str[k]);
if( ( (c >= 'A') && (c <= 'Z')) || (str[k] == ' '))
str[i++]=str[k];
}
str='\0';

T[ti] = malloc(strlen(str)+1);
strcpy(T[ti],str);

ti++;
}
}

for(i=0; i<pi; i++)
{
printf("\n%d: ", i+1);
for(j=0; j<ti; j++)
if( search(threshold, P, T[j]) )
printf("%d ", j+1);
}
}


int search(int separation, char *profile, char *title)
{
int p,t,pi,ti, index;
char* pwords[256], *twords[256];
char* pword, *tword;
char* str;

str = (char*)malloc(strlen(profile)+1);
strcpy(str, profile);
pword = (char*)strtok(str, " ");
pwords[0] = (char*)malloc(strlen(pword)+1);
strcpy(pwords[0],pword);
for(pi=1; (pword=(char*)strtok(NULL, " ")) != NULL; pi++)
{
pwords[pi] =(char*)malloc(strlen(pword)+1);
strcpy(pwords[pi], pword);
}

str = (char*)malloc(strlen(title)+1);
strcpy(str, title);
tword = (char*)strtok(str, " ");
twords[0] = (char*) malloc(strlen(tword)+1);
strcpy(twords[0], tword);
for(ti=1; (tword=(char*)strtok(NULL, " ")) != NULL; ti++ )
{
twords[ti] = (char*)malloc(strlen(tword)+1);
strcpy(twords[ti], tword);
}

index=-1;
for(p=0; p<pi; p++ )
{
for(t=0; t< ti; t++)
{
printf("comparing %s and %s\n", pwords[p], twords[t]);
if (strcasecmp(pwords[p], twords[t]) == 0 )
{
printf("index: %d, t: %d, separation: %d\n", index, t, separation);
if(index==-1)
{
index=t;
}
else if ( abs(t-index) == (separation+1))
{
printf("FOUND!!!\n");
return 1;
}
}
}
}

return 0;

}


/* @END_OF_SOURCE_CODE */

[sweko]

The name of your algo said it all. I guess you go in a recursion to deep for the Online Judge call stack.

BTW, you should use BBCode formating when sending source code to the forum, it's much more readable.

Also, we don't have to know your Judge ID

[monika]

Hi,

Thanks for the reply

My program doesn't uses recursion. It was only a copy-paste form an earleir problem!

And ok, I managed to get rid of SIGSEGV. It was due to inadequate memory allocation!!!!

But now I'm getting WA!
Any hints???

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>


void main()
{
    int search(int, char*, char*);

    int pi=0, ti=0;
    char *P[50], *T[250];
    int threshold[50];
    int i,j,k;

    char c;
    char str[256];

    while( (c=getchar()) != '#')
    {
        if( (c == 'P') && (pi < 50) )
        {
            scanf("%*c%d%[^\n]s", &threshold[pi],str);
            P[pi] = (char*)malloc(strlen(str)+1);
            strcpy(P[pi],str);
            pi++;

        }
        else if ((c == 'T') && (ti < 250) )
        {
            scanf("%*c%[^|]s", str);

            for(i=0,k=0; k<strlen(str); k++)
            {
               c = toupper(str[k]);
               if( ( (c >= 'A') && (c <= 'Z')) || (str[k] == ' '))
                  str[i++]=str[k];
            }
            str[i]='\0';

            T[ti] = (char*)malloc(strlen(str)+1);
            strcpy(T[ti],str);

            ti++;
        }
    }
    pi--;ti--;

    printf("pi: %d, ti: %d\n", pi, ti);

    for(i=0; i<=pi; i++)
    {
       printf("\n%d: ", i+1);
       for(j=0; j<=ti; j++)
           if( search(threshold[i], P[i], T[j]) )
              printf("%d ", j+1);
    }

}


int search(int separation, char *profile, char *title)
{
   int p,t,pi,ti, index;
   char* pwords[256], *twords[256];
   char* pword, *tword;
   char* str;

   int wordnum[255];
   int i,j;

   str = (char*)malloc(strlen(profile)+1);
   strcpy(str, profile);
   pword = (char*)strtok(str, " ");
   pwords[0] = (char*)malloc(strlen(pword)+1);
   strcpy(pwords[0],pword);
   for(pi=1;  (pword=(char*)strtok(NULL, " ")) != NULL; pi++)
   {
        pwords[pi] =(char*)malloc(strlen(pword)+1);
        strcpy(pwords[pi], pword);
   }

   str = (char*)malloc(strlen(title)+1);
   strcpy(str, title);
   tword = (char*)strtok(str, " ");
   twords[0] = (char*) malloc(strlen(tword)+1);
   strcpy(twords[0], tword);
   for(ti=1; (tword=(char*)strtok(NULL, " ")) != NULL; ti++ )
   {
        twords[ti] = (char*)malloc(strlen(tword)+1);
        strcpy(twords[ti], tword);
   }

   memset(wordnum, 0, sizeof(wordnum));
   index=0;
   for(p=0; p<pi; p++ )
   {
      for(t=0; t< ti; t++)
      {
         if (strcasecmp(pwords[p], twords[t]) == 0 )
            wordnum[index++]=t;
      }
   }

   for(i=0;i<index;i++)
   {
      for(j=0;j<index;j++)
          if( (i != j) && (abs(wordnum[i] - wordnum[j]) <= (abs(separation) + 1)))
             return 1;
   }

   return 0;

}


/* @END_OF_SOURCE_CODE */

[luzi82]

this code is right in sample but WA
please tell me a fail example if you find any error

[cpp]
#include <iostream.h>
#include <stdio.h>

main() {
char profiles[50][1024];
int profiles_id[50][1024];
int profiles_gap[50];
int profiles_max = 0;
int profiles_now_id = 0;
char title[255][256];
int title_id[255][256];
int title_max = 0;
int title_now_char = 0;
int title_now_id = 0;
char input[1024];
int i1, i2, i3, i4;
bool b1, b2, b3;
bool ting = false;

// input section
while (true) {
gets(input);
if ( input[0] == '#' && !ting ) {
break;
} else if ( input[0] == 'P' && !ting ) {
i1 = 0;
i2 = 0;
while( input[i1] < '0' || input[i1] > '9' ) {
i1++;
}
do {
i2 *= 10;
i2 += input[i1] - (int)'0';
i1++;
} while( input[i1] >= '0' && input[i1] <= '9' );
//cout << i2 << endl;
profiles_gap[profiles_max] = i2;
i2 = 0; //profiles index
i3 = 0; //profiles id index
b1 = false; //writing profiles string
while( input[i1] != '\n' && input[i1] != '\0' ) {
if ( input[i1] >= 'A' && input[i1] <= 'Z' ) {
input[i1] += 'a' - 'A';
} else if ( input[i1] == ' ' ) {
b1 = false;
}
if ( input[i1] >= 'a' && input[i1] <= 'z' ) {
if ( !b1 ) {
profiles_id[profiles_max][i3] = i2;
i3++;
b1 = true;
}
profiles[profiles_max][i2] = input[i1];
i2++;
}
i1++;
}
profiles[profiles_max][i2] = 0;
profiles_id[profiles_max][i3] = i2;
profiles_id[profiles_max][i3+1] = -1;

/*
for ( i1 = 0 ; profiles[profiles_max][i1] > 0 ; i1++ ) {
cout << profiles[profiles_max][i1];
}
cout << endl;
for ( i1 = 0 ; profiles_id[profiles_max][i1] >= 0 ; i1++ ) {
cout << profiles_id[profiles_max][i1] << " ";
}
cout << endl;
*/

profiles_max++;
} else if ( ting || input[0] == 'T' ) {
if ( !ting ) {
title_now_char = 0;
title_now_id = 0;
i1 = 2;
} else {
i1 = 0;
}
ting = true;
b1 = false; //writing title string
while( input[i1] != '\n' && input[i1] != '\0'
&& input[i1] != '|' ) {
if ( input[i1] >= 'A' && input[i1] <= 'Z' ) {
input[i1] += 'a' - 'A';
} else if ( input[i1] == ' ' ) {
b1 = false;
}
if ( input[i1] >= 'a' && input[i1] <= 'z' ) {
if ( !b1 ) {
title_id[title_max][title_now_id] = title_now_char;
title_now_id++;
b1 = true;
}
title[title_max][title_now_char] = input[i1];
title_now_char++;
}
i1++;
}
if ( input[i1] == '|' ) {
title[title_max][title_now_char] = 0;
ting = false;
title_id[title_max][title_now_id] = title_now_char;
title_id[title_max][title_now_id+1] = -1;
/*
for ( i1 = 0 ; title[title_max][i1] > 0 ; i1++ ) {
cout << title[title_max][i1];
}
cout << endl;
for ( i1 = 0 ; title_id[title_max][i1] >= 0 ; i1++ ) {
cout << title_id[title_max][i1] << " ";
}
cout << endl;
*/

title_max++;
}
} else {
while(true); // happy loop to crash the ass!!!
}
}

// output section
for ( i1 = 0 ; i1 < profiles_max ; i1++ ) {
b3 = false;
cout << i1+1 << ": ";
for ( i2 = 0 ; i2 < title_max ; i2++ ) {
i3 = -1; // profiles_gap count
b1 = false; // title and profiles matched
title_now_id = 0;
while ( title_id[i2][title_now_id+1] > 0 && !b1 ) {
profiles_now_id = 0;
b2 = false; // match a word
while ( profiles_id[i1][profiles_now_id+1] > 0 && !b2 ) {
if ( title_id[i2][title_now_id+1]
- title_id[i2][title_now_id]
== profiles_id[i1][profiles_now_id+1]
- profiles_id[i1][profiles_now_id] ) {
b2 = true;
for ( i4 = 0 ; i4 < title_id[i2][title_now_id+1]
- title_id[i2][title_now_id] && b2 ; i4 ++ ) {
if ( title[i2][title_id[i2][title_now_id] + i4] !=
profiles[i1][profiles_id[i1][profiles_now_id]
+ i4] ) {
b2 = false;
}
}

/*
if ( b2 ) {
for ( i4 = 0 ; i4 < title_id[i2][title_now_id+1]
- title_id[i2][title_now_id] && b2 ; i4 ++ ) {
cout << profiles[i1][profiles_id[i1][profiles_now_id] + i4];
}
cout << endl;
}
*/

}
profiles_now_id++;
}
if ( b2 ) {
if ( i3 >= 0 ) {
b1 = true;
} else {
i3 = profiles_gap[i1]+1;
}
}
title_now_id++;
i3--;
}
if ( b1 ) { // if matched
if ( b3 ) {
cout << ",";
}
cout << i2 + 1;
b3 = true;
}
}
cout << endl;
}
}

[/cpp]

[luzi82]

oh i am thinking.........
in the sample

P: 1 art rock metaphor concepts

is it mean that there exist 2 pair

art -- rock
metaphor -- concepts

the result match only when one pair above is found in the title, separated by no more than 1 word?

[Pedrinho UFPE]

Hi people,
I'm getting WA in this problem. But I think there's some ambiguities. Can anyone who had AC explain those ambiguities? Thanks.

1) If we have a profile with more than 2 words, we have to search for All the pairs that we can have (a) with the K words or aonly pair by pair (b)?
Example:
a - 3 abc def hij ooo
search abc - def, abc - hij, abc - ooo, def-hij, def-ooo, hij-ooo, def-abc, hij-abc, ooo-abc, hij-def, ooo-def, ooo-hij.
b - 3 abc def hij ooo
search abc-def, def-abc, hij-ooo,ooo-hij.

2) We have to output:
1:1,2
2: (<- without a space)
3:1,2,3,4
or
1: 1,2
2: (<- with a space)
3: 1,2,3,4

Thanks again.

Pedro

[ChristopherH]

After a bunch of investigation, I think I have found some of the ambiguities which are causing many of us problems.

First, to answer your specific question, we are indeed intended to consider all possible pairings, not just adjacent keywords.

The big issue is that the judge's input contains duplicate words in profiles: you can't treat a profile as a *set* of keywords.

For the input:

P: 0 aa bb
P: 0 aa bb aa
T: aa|
T: aa aa|
T: aa bb|
#

My AC solution gives:

1: 3
2: 2,3

The results for the second profile are surprising: if a word is duplicated in the profile, the judge expects us to consider two occurances of that word within the window to be a hit.

I think the problem was unfortunately underspecified in this regard. It hinges on the interpretation of the phrase "a pair of keywords". Used informally, "pair" usually has connotations of distinctness. I personally think it's more natural to interpret the problem as looking for distinct words, and spent a lot of time experimenting before figuring out what the judge actually wanted.

On the presentation issue, it appears that one is expected to remove all trailing whitespace.

[PMNOX]

so the correct time for this problem i P * T * (n_of_words)^2 ?

[Abednego]

Yes, P * T * (n_of_words)^2 is fast enough.

I found that reading words with "cin>>" and then stripping off all non-alphabetic characters works just fine. There is no need for fancy finite state machines.

[Jan]

You have to consider all pairs.

Code: Select all

P: 1 art rock metaphor concepts
art rock
art metaphor
art concepts
rock art
rock metaphor
rock concepts
...

The answer of your second question is yes.

[rickyliu]

The results for the second profile are surprising: if a word is duplicated in the profile, the judge expects us to consider two occurances of that word within the window to be a hit.

I think the problem was unfortunately underspecified in this regard. It hinges on the interpretation of the phrase "a pair of keywords". Used informally, "pair" usually has connotations of distinctness. I personally think it's more natural to interpret the problem as looking for distinct words, and spent a lot of time experimenting before figuring out what the judge actually wanted.

I don't agree. In reality, one could search with 2 or more same keywords. I considered this case at the early beginning.

On the presentation issue, it appears that one is expected to remove all trailing whitespace.

When there are no titles found, there is a space after the colon. You can *see* it in the sample output. I omitted it and got PE. It took me awhile to figure it out.

[brianfry713]

It looks like this line from the problem statement is not met in the judge's input:
No title will be longer than 255 characters

However no line is longer than 80 characters and there are no more than 255 words in a title.