698 - Index

[wyvmak]

I just hate it when I knew the sample output is wrong. If sample output is wrong, what is its purpose? or in the real ACM, wrong sample output is part of the test for competitors? Yet, I still cannot get AC.

would someone be kind enough to give me the output for the following input:

abc
def

abc abc def
abc abc def def
abc abc def def def
abc

would it be:
Case 1
ABC 1, 1-2, 2-3, 3-4
DEF 1-2, 2-3, 3, 3

Also, will there be a case that there's zero word to be indexed?
Or what other tricks in it?

[Adrian Kuegel]

I would say, the output is
Case 1
ABC 1-4
DEF 1-3
but I also get WA. What is the correct output for this input?
2fOr1
.*the+
bla

blab the+ h2for1
2for1z 2for1 *the bla
blabla the

My program prints:
Case 1
2FOR1 2
BLA 2
THE 1-3

[Ivan Golubev]

My accepted solution produces this output:

For wyvmak's input:
Case 1
ABC 4
DEF 1-3

For Adrian's input:
Case 1
2FOR1 2
BLA 2

[Adrian Kuegel]

Ivan, thank you for your reply. But I don't understand, why the output for ywyvmak's input is "ABC 4" and not "ABC 1-4". And can you explain, why your program does not print the "the" for my input. Because it is said in the description: "Punctuation preceding or following an index term will be ignored." What does it mean?

[Ivan Golubev]

Oops, I've used a bit incorrect input file (there was a space after ABC). So real output is 'ABC 1-4', of course.

About 'the': I think (and it can be check with asserts, lazy to do it by my own ) that terms doesn't contains anything else than digits and letters. My solution reads them as is. I've done searching via strstr. If before and after term there something else than letters and digits then it's match.

[Rossi]

why compile error hah! runs great on VC6.0 problem-698
[cpp]
#include <iostream>
#include <vector>
#include <cctype>
#include <functional>
#include <algorithm>

using namespace std;

char *strUpper(char *);
char *getToken(char *);

class Word{
public:
char word[12];
vector<int> lst;

Word(char *str)
{
strcpy(word, strUpper(str));
lst.clear();
}
};

class Compare:binary_function<Word, Word, bool>{
public:
result_type operator()(first_argument_type A, second_argument_type B)
{
return (result_type)(!(strcmp(A.word, B.word) > 0));
}
};

char str[10000000L];

int main()
{
int set = 0, lnum;
char *p;

vector<Word> listOfWords;
vector<Word>::iterator iter;
vector<int>::iterator i;

while(gets(str)){
if(str[0] == NULL)
break;

if(!listOfWords.empty())
listOfWords.clear();

while(str[0]){
Word toPush(str);
listOfWords.push_back(toPush);
gets(str);
}

sort(listOfWords.begin(), listOfWords.end(), Compare());

gets(str);
for(lnum = 1; str[0]; lnum++){
strUpper(str);

p = getToken(str);
while(p){
iter = listOfWords.begin();
while(iter != listOfWords.end()){
int cmp = strcmp(p, iter->word);

if(cmp == 0){
iter->lst.push_back(lnum);
break;
}
else if(cmp < 0)
break;

iter++;
}
p = getToken(NULL);
}
gets(str);
}

cout << "Case " << ++set << endl;

for(iter = listOfWords.begin(); iter != listOfWords.end(); iter++){
if(!iter->lst.empty()){
i = iter->lst.begin();
cout << iter->word << " " << *i++;

for(bool seq = false; i != iter->lst.end(); i++){
switch(*i - *(i - 1)){
case 0:
break;
case 1:
seq = true;
break;
default:
if(seq){
cout << "-" << *(i - 1) << ", " << *i;
seq = false;
}
else
cout << ", " << *i;
break;
}
}
if(seq)
cout << "-" << *(i - 1);
cout << endl;

iter->lst.clear();
}
}
cout << endl;
}
return 0;
}

char *strUpper(char *in)
{
char *p = in;

while(*p){
*p = toupper(*p);
p++;
}
return in;
}

char *getToken(char *str)
{
static char *p;
char *q;

if(str)
p = str;

if(p == NULL)
return NULL;

while(!(isdigit(*p) || isalpha(*p)) && *p)
p++;

q = p;
while(isdigit(*p) || isalpha(*p))
p++;

if(*p == NULL)
p = NULL;
else
*p++ = NULL;

return q;
}

[/cpp]

[suman]

hi,
The following modification of your code compiles under g++ cygwin. You made some mistakes. Try looking at the changes. The OJ uses differnent compiler which is obviously better than VC++6.0. Try the dev-cpp which is a windows port of gcc. You can find it at http://www.sourceforge.net.


[cpp]
#include <cstdio>
#include <iostream>
#include <vector>
#include <cctype>
#include <functional>
#include <algorithm>

using namespace std;

char *strUpper(char *);
char *getToken(char *);

class Word{
public:
char word[12];
vector<int> lst;

Word(char *str)
{
strcpy(word, strUpper(str));
lst.clear();
}
};

class Compare:binary_function<Word, Word, bool>{
public:
result_type operator()(first_argument_type A, second_argument_type B)
{
return (result_type)(!(strcmp(A.word, B.word) > 0));
}
};

char str[10000000L];

int main()
{
int set = 0, lnum;
char *p;

vector<Word> listOfWords;
vector<Word>::iterator iter;
vector<int>::iterator i;

while(gets(str)!=0){
if(str[0] == 0)
break;

if(!listOfWords.empty())
listOfWords.clear();

while(str[0]){
Word toPush(str);
listOfWords.push_back(toPush);
gets(str);
}

sort(listOfWords.begin(), listOfWords.end(), Compare());

gets(str);
for(lnum = 1; str[0]; lnum++){
strUpper(str);

p = getToken(str);
while(p){
iter = listOfWords.begin();
while(iter != listOfWords.end()){
int cmp = strcmp(p, iter->word);

if(cmp == 0){
iter->lst.push_back(lnum);
break;
}
else if(cmp < 0)
break;

iter++;
}
p = getToken(NULL);
}
gets(str);
}

cout << "Case " << ++set << endl;

for(iter = listOfWords.begin(); iter != listOfWords.end(); iter++){
if(!iter->lst.empty()){
i = iter->lst.begin();
cout << iter->word << " " << *i++;
bool seq;

for(seq = false; i != iter->lst.end(); i++){
switch(*i - *(i - 1)){
case 0:
break;
case 1:
seq = true;
break;
default:
if(seq){
cout << "-" << *(i - 1) << ", " << *i;
seq = false;
}
else
cout << ", " << *i;
break;
}
}
if(seq)
cout << "-" << *(i - 1);
cout << endl;

iter->lst.clear();
}
}
cout << endl;
}
return 0;
}

char *strUpper(char *in)
{
char *p = in;

while(*p){
*p = toupper(*p);
p++;
}
return in;
}

char *getToken(char *str)
{
static char *p;
char *q;

if(str)
p = str;

if(p == NULL)
return NULL;

while(!(isdigit(*p) || isalpha(*p)) && *p)
p++;

q = p;
while(isdigit(*p) || isalpha(*p))
p++;

if(*p == 0)
p = 0;
else
*p++ = 0;

return q;
}

[/cpp]

Good luck.

- Suman

[Rossi]

Thankx a lot........

[sjn]

oh, i got TLE

can anyone help me?

[titid_gede]

can you tell me what is the trickies input for this problem? always got WA after almost 10 submissions

regards,
titid

[little joey]

All the obvious trickies are in the sample input. Everything more would be a spoiler.

One advise: Don't assume anything that's not explicitly written in the problem description. I did that and got 10+ WAs before finaly getting AC.

[bobi1978]

little joey wrote:

Code: Select all

One advise: Don't assume anything that's not explicitly written in the problem description. 

What do you mean by this?

1) In the INDEX list, if there is a character that is not ALPHA_NUM what should I do with it?
ex:--- INDEX LIST ---

//foR*
ab*c<>
?a?b?

What are the Indexes in this list?

FOR AB A

or

FOR ABC AB
?

[little joey]

There are no such cases; that would violate the description.
As I said, I'm not gonna give a spoiler.

[Aleksandrs Saveljevs]

Well, I managed to get it AC recently.

In the end, having only REs, beseeching God he would let me have WA, suddenly, to my astonishment, it was AC.

There are several found-out things I would like to share:

1) Words can be longer than 10 symbols, but shorter than 21 (maybe it results from 10 letters plus 10 digits; though it contradicts to what is said in the sample input). It may be not so if one can get SIGABRT because of something else than assert().

2) Either lines can be longer than 25000 symbols or there are less than 2 blank lines in the end.

If any of the above statements are wrong, please, make a post, so that people wouldn't have so much problems.

[minskcity]

I've already got 10 WA, can anybody tell me what I'm missing? Any special cases? HELP, PLEASE... [cpp]#include <iostream>
#include <string>
#include <fstream>
#include <ctype.h>
#include <vector>
#include <map>
using namespace std;

map < string, vector < long > > index;
vector < long > empty;
string s;
long t;

int main(){

// ifstream cin("in.txt");

t = 1;
while(getline(cin, s)){

index.clear();

while(s.size()){ // storing index words
for(unsigned i = 0; i < s.size(); i++) s = toupper(s);
index[s] = empty;
getline(cin, s);
}

long cnt = 0;
while(getline(cin, s) && s.size() && ++cnt){ // inserting to index lines of word that match
s += ' ';
string word = "";

for(unsigned i = 0; i < s.size(); i++){
s = toupper(s);
if(isalnum(s)) word += s;
else{
if(index.find(word) != index.end() && (!index[word].size() || index[word].back() != cnt))
index[word].push_back(cnt);
word = "";
}
}

}

cout << "Case " << t++ << endl; // starting to print answer

for(map < string, vector < long > > :: iterator it = index.begin(); it != index.end(); it++)
if(it->second.size()){
cout << it->first;
for(unsigned i = 0; i < it->second.size(); i++){
if(i + 1 == it->second.size() || it->second + 1 != it->second[i + 1]){
cout << " " << it->second;
if(i + 1 != it->second.size()) cout << ",";
}else{
long st = i;
while(i + 1 < it->second.size() && it->second + 1 == it->second[i + 1]) i++;
cout << " " << it->second[st] << "-" << it->second;
if(i + 1 != it->second.size()) cout << ",";
}
}
cout << endl;
}

cout << endl;

}

return 0;
}
[/cpp]