10815 - Andy's First Dictionary

[Sanny]

Problem description says that number of distinct words will be less than 5000. But you're assuming total number of words to be less than 5000.

[watershed]

Who can help me solve this problem, thanks~

Code: Select all

#include<iostream>
#include<string>
#include<set>
using namespace std;
main()
{
	set<string> words;
	string buffer="", word="";
	while( cin >> buffer ) {
		int len = buffer.length();
		for(int i=0; i<=len; ++i) {
			if( buffer[i] >= 'A' && buffer[i] <= 'Z' )
					word+=tolower(buffer[i]);
			else if( buffer[i] >= 'a' && buffer[i] <= 'z' )
					word+=buffer[i];
			else if( word != "" ) {
					words.insert(word);
					word="";
			}
		}			
	}
	set<string>::iterator p;
	for(p=words.begin(); p!=words.end(); ++p)
		cout << *p << endl;
}

[Martin Macko]

Code: Select all

		int len = buffer.length();
		for(int i=0; i<=len; ++i) {

Shouldn't it be i < len ?

[FAQ]

Code: Select all

ACed

[Martin Macko]

Have you tried any really huge input? What about 5000 random words of length something about 200 chars?

[FAQ]

Yes, I have tried an input with 5000 lines, and string[200] 'aaaaa..a' for each line, and it runs well

[Martin Macko]

Yes, I have tried an input with 5000 lines, and string[200] 'aaaaa..a' for each line, and it runs well

Just try random strings. But do not forget to check you are not using more that 32MB ram, eg. by ulimit if you are using linux.

[_.B._]

Greetings FAQ!
For this problem I considered all words to be <= than 200 chars long, and no more than 50000 words in Andy's Dictionary (maybe a lot less than that would work).
Quick Sort did the work, and just don't print the repeated words.
Remember all words must be lowercase.
Ah!, and either tokenize lines, or build words char-by-char.

Hope it helps.

[FAQ]

Thanks a lot Martin, _.B._. I got AC now

[smilitude]

Grrr....

runtime error!

Code: Select all

/*
10815 - andy's first dictionary
submission 1 runtime error!  2 output limit exceeded!
coded at 4:42 on 6th oct 05
*/

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


int sort_function(const void *a, const void *b) {
	return strcmp((char *)a, (char *)b);
}

int main() {
	//declaration 
	char line[205];
	char words[5005][205];
	char current_word[205];
	int i,j,len,k;
	int total=0;

    while(1){
	//input taking 
	while(gets(line)!=NULL) {
		len=strlen(line);
	//choosing word - lowering and then saving them
		for(i=0;i<len;i++) {
			j=0;
			while(isalpha(line[i])) {
				current_word[j]=line[i];
				j++;i++;
			}

			current_word[j]=NULL;
			for(k=0;k<j;k++) 
				current_word[k]=tolower(current_word[k]);
            for(j=0;j<total;j++)
                if(strcmp(current_word,words[j])==0)break;
            if(j==total)
                strcpy(words[total++],current_word);
		}
	}
	

	//sorting the whole dictionary
		qsort(words,total,sizeof(words[0]),sort_function);

	//output routine
		for(i=1;i<total;i++) {
			//if(strcmp(words[i]," "));			
           if(words[i][0]!=' ')
            printf("%s\n",words[i]);
		}
}		
		return 0;
}
		
	

[sunny]

fahim
i didn't read your code fully. in this problem you should make your arraysize for the words much bigger. There are 5000 distinct words. but
more than 5000 words which are same to any others. one other thing you should declare large arrays globally unless there's a chance for RTE.

[smilitude]

code edited....
now what's wrong?

here it checks every single new word, whether they are really new or not

[jjtse]

Hey fellas,

I've been working on this problem for a while now. Finally got it to work correctly. The only problem now is that it's getting a presentation error. I bet it's something trivial, it's just that I can't see it. I tried putting/removing the newline at the end of the output file. That didn't make a difference. Can someone run this on their machine with the correct version of the compiler and let me know where I presented my data wrong? Thanks. This is what I have:

Code: Select all

code removed...

[jjtse]

does anyone know what was wrong with watershed's code? Apparently, I'm having the same problem he used to have. I compared the output produce by my codes with the output produced by his codes, and it looks exactly the same. Mine, however, has presentation error instead of wrong answer, and I can't see where I'm presenting it wrong.

[Martin Macko]

Code: Select all

  while (!cin.eof()){
    s = "";
    while (isalpha(c)){
      s.push_back(c);
      if (cin.eof())
        break;
      c=cin.get();
    }
    insert(s);

If the input begins with a non-alpha character your output contains the empty word "".