175 - Keywords

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by 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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by 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
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am

175: SIGSEGV

Post by 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
New poster
Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm

Post by 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 :lol:
SWeko has spoken

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am

Post by monika »

Hi,

Thanks for the reply :D

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
New poster
Posts: 4
Joined: Wed Oct 16, 2002 3:18 pm

175 WA crazy

Post by 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
New poster
Posts: 4
Joined: Wed Oct 16, 2002 3:18 pm

Post by 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
New poster
Posts: 15
Joined: Tue Sep 10, 2002 1:56 am
Location: Brasil
Contact:

175 - Keywords

Post by 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
Interested

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by 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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX »

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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

ChristopherH wrote: 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 175 - Keywords

Post by 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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”