10815 - Andy's First Dictionary

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

Moderator: Board moderators

kissu parina
New poster
Posts: 19
Joined: Thu May 20, 2010 8:58 am

Re: 10815 - Andy's First Dictionary

Post by kissu parina » Sun Feb 06, 2011 7:03 am

easy problem...just keep in mind that
andy's-->>
andy
s

not andys..... :)
one day...

cool
New poster
Posts: 2
Joined: Mon Feb 14, 2011 6:45 am

Re: 10815 - Andy's First Dictionary

Post by cool » Thu Feb 17, 2011 5:39 am

can any one help me please :(

i am getting TLE

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10815 - Andy's First Dictionary

Post by plamplam » Fri Jul 08, 2011 12:56 pm

Use a faster sorting algorithm (I think you are using bubble-sort) to sort the words in dictionary order. I used qsort to get AC in 0.115 seconds. Good luck.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

AbdoAdel
New poster
Posts: 1
Joined: Mon Aug 22, 2011 12:22 pm

Re: 10815 - Andy's First Dictionary

Post by AbdoAdel » Mon Aug 22, 2011 12:29 pm

Hi, this is my first post here :)
im getting a WA
this is my code :

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;

void parseLine(const string& line, set<string>& words);
string removePunctAndConvertToLowerCase(const string& word);

int main() {
	string line;
	set<string> words;
	while (getline(cin, line))
		if (line != "")
			parseLine(line, words);
	for (set<string>::iterator it = words.begin(); it != words.end(); it++)
		cout << (*it) << endl;
	return 0;
}

void parseLine(const string& line, set<string>& words) {
	stringstream ss(stringstream::in | stringstream::out);
	ss << line;
	while (!ss.eof()) {
		string word;
		ss >> word;
		word = removePunctAndConvertToLowerCase(word);
		if (word != "" && words.find(word) == words.end())
			words.insert(word);
	}
}

string removePunctAndConvertToLowerCase(const string& word) {
	string tmp;
	for (int i = 0; i < (int) word.length(); i++) {
		if (isalpha(word[i]))
			tmp += tolower(word[i]);
	}
	return tmp;
}
General idea: i read a string containing one line, if that line is not empty, then ( parseLine ) parses it to words using string streams, removes punctuation and converts to lower case form and then check if it is not listed before
I would be very thankful if some one helped :wink:

Joarder
New poster
Posts: 3
Joined: Mon Nov 28, 2011 11:26 pm

Getting WA in 10815 - Andy's First Dictionary

Post by Joarder » Mon Nov 28, 2011 11:53 pm

Why my code getting WA...??? :roll: :roll: :roll:
Plz.... Someone Cheak it...
or Give me some test cases...
here is my code....

/*
* File: 10815 - Andy's First Dictionary.cpp
* Tag: String
* http://uva.onlinejudge.org/external/108/10815.html


* Runtime:
* Author: Shoshi
* Created on November 28, 2011, 9:00 PM
*/

#pragma warning (disable : 4786)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

using namespace std;

int main() {
//freopen("10815 - Andy's First Dictionary_in.txt", "r", stdin);
map<string,bool>m;
map<string,bool>::iterator it;
string str,str1;
int l,i;
while(cin>>str) {
l=str.length();
str1.clear();
for(i=0;i<l;i++) {
if((str>='A' && str<='Z') || (str>='a' && str<='z') || (str>='0' && str<='9')) {
str=tolower(str);
str1+=str;
}
else {
str.erase(i,1);
i--;
l--;
if(!str1.empty()) {
m[str1]=true;
str1.clear();
}
}
}
if(!str1.empty()) {
m[str1]=true;
str1.clear();
}
}
for(it=m.begin();it!=m.end();it++)
cout<<(*it).first<<endl;
return 0;
}

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10815 - Andy's First Dictionary

Post by sith » Tue Jun 19, 2012 5:01 pm

Hello

Why my solution is wrong?

Code: Select all

class Main {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        try {
            Set<String> result = new HashSet<String>();
            while ((line = reader.readLine()) != null) {

                StringTokenizer tokenizer = new StringTokenizer(line, " !\"#$%&'()*+,-./0123456789:;<=>?@[]^_`{|}~");
                while (tokenizer.hasMoreTokens()) {
                    result.add(tokenizer.nextToken().toLowerCase());
                }
            }
            String[] words = result.toArray(new String[result.size()]);
            Arrays.sort(words);

            for (String word : words) {
                System.out.println(word);
            }
        }
        catch (IOException e) {

        }
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10815 - Andy's First Dictionary

Post by brianfry713 » Tue Jun 19, 2012 11:30 pm

This code doesn't compile. Post the full code with the imports.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10815 - Andy's First Dictionary

Post by sith » Wed Jun 20, 2012 11:06 am

Sorry. Here is the full code

Code: Select all

AC
Last edited by sith on Thu Jun 21, 2012 12:40 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10815 - Andy's First Dictionary

Post by brianfry713 » Wed Jun 20, 2012 10:40 pm

For an input file containing:

Code: Select all

a\bc
My AC output is:

Code: Select all

a
bc
I used the c function isalpha().
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10815 - Andy's First Dictionary

Post by sith » Thu Jun 21, 2012 12:40 pm

Thanks, it works

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: Getting WA in 10815 - Andy's First Dictionary

Post by mgavin2 » Tue Jul 31, 2012 11:09 pm

Joarder wrote:

Code: Select all

int main() {
	//freopen("10815 - Andy's First Dictionary_in.txt", "r", stdin);
	map<string,bool>m;
	map<string,bool>::iterator it;
	string str,str1;
	int l,i;
	while(cin>>str) {
		l=str.length();
		str1.clear();
		for(i=0;i<l;i++) {
			if((str[i]>='A' && str[i]<='Z') || (str[i]>='a' && str[i]<='z') || (str[i]>='0' && str[i]<='9')) {
				str[i]=tolower(str[i]);
				str1+=str[i];
			}
			else {
				str.erase(i,1);
				i--;
				l--;
				if(!str1.empty()) {
					m[str1]=true;
					str1.clear();
				}
			}
		}
		if(!str1.empty()) {
			m[str1]=true;
			str1.clear();
		}
	}
	for(it=m.begin();it!=m.end();it++)
		cout<<(*it).first<<endl;
	return 0;
}
Ok, it seems like you try your best to pull out punctuation and sort that situation out. So with input like "help.me" you get help and me, but if you hit a word that's possessive, then you're screwed.

eg. It was the dog's job to bark at the mailman.

you would end up with the word "s" in your list... Perhaps you should try to filter out any one letter words that aren't A or I?

Also when you need a set of unique elements, just use the set datatype
eg.

Code: Select all

#include <set>
#include <string>
using std::set;
using std::string;
set<string> words;
try to find a resource to explain more about it :)
all that matters is AC

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: Getting WA in 10815 - Andy's First Dictionary

Post by mgavin2 » Tue Jul 31, 2012 11:53 pm

also perhaps contractions in words : http://en.wikipedia.org/wiki/Contraction_(grammar)
all that matters is AC

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: Getting WA in 10815 - Andy's First Dictionary

Post by mgavin2 » Wed Aug 01, 2012 12:42 am

Nevermind. I don't think it matters. I think your problem is accepting characters of '0'-'9' when it says in the problem statement "a word is defined as a consecutive sequence of alphabets, in upper and/or lower case. Words with only one letter are also to be considered." ...

after trying to solve it now I'm stuck in WA too. WAwsome.
all that matters is AC

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: Getting WA in 10815 - Andy's First Dictionary

Post by uvasarker » Sun Sep 02, 2012 1:18 pm

I am getting TLE help me.........please

Code: Select all

/* Removed */
Thanks guru (brianfry713).
I got AC
Last edited by uvasarker on Fri Sep 07, 2012 2:51 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Getting WA in 10815 - Andy's First Dictionary

Post by brianfry713 » Wed Sep 05, 2012 1:39 am

Try rewriting it without using strtok, just test each character to see if it's a-z or A-Z. Also try sorting directly instead of using a map. Your tolow function is also going to be slow.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 108 (10800-10899)”