10999 - Crabbles
Moderator: Board moderators
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
No, I use a hashtable, not a trie, and I didn't do it during the contest, although a hashtable isn't too difficult to code. I don't store the strings of the dictionary but I use an encoding that guarantees that if two strings are anagrams they produce the same code, but if they're not they produce different codes. Then I store the codes in the hashtable (in constant time per code), so I can verify if a particular code is in the hashtable in (almost) constant time.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
I have an another question.
I also know how hashing works, and how trie works, (and surely how BST or set-dictionary works, too),
but in this situation how should I implement tries?
|∑| = 26, i.e. the number of available letter is 26 ('a' through 'z'),
and almost string's LENGTH is about 10,
so brute-force implementation requires too much memory.
although I use 26-ary tree using linked list and pointer,
it seems that it needs too much memory.
Can you help me ?
I also know how hashing works, and how trie works, (and surely how BST or set-dictionary works, too),
but in this situation how should I implement tries?
|∑| = 26, i.e. the number of available letter is 26 ('a' through 'z'),
and almost string's LENGTH is about 10,
so brute-force implementation requires too much memory.
although I use 26-ary tree using linked list and pointer,
it seems that it needs too much memory.
Can you help me ?
Sorry For My Poor English.. 

-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
You can encode strings into numbers, if you looked at the constraint enough..
Check out http://www.algorithmist.com !
To wook: I'm using a trie, too. With child-sibling representation it fits well in memory limit (see http://www.nist.gov/dads/HTML/binaryTreeRepofTree.html for basic information on that)
I used a straight-forward (each node having 26 pointers to child nodes, and a bool telling whether the node represents a word in the dictionary) trie implementation during the contest and if I remember correctly, it used roughly 12mb of memory. It should be possible to construct test cases where this implementation uses more than 32mb of memory, though.wook wrote:I have an another question.
I also know how hashing works, and how trie works, (and surely how BST or set-dictionary works, too),
but in this situation how should I implement tries?
|∑| = 26, i.e. the number of available letter is 26 ('a' through 'z'),
and almost string's LENGTH is about 10,
so brute-force implementation requires too much memory.
although I use 26-ary tree using linked list and pointer,
it seems that it needs too much memory.
Can you help me ?
GREAT!!! After several TLE i finally got AC and used 0.66. I did it with insert sort, and i think there may be no worse case, so i got TLE, and then i decided using heap sort, and it is greated changed. I am happy
. To more algorithmus , I shall say, i use c and so only array for dictionary, and also backtracking for all words which can be made from given 10 letters. And i sort all words in the dictionary so that i can use binary search within the array and also the given letters will be sorted so that the order look the same as in the dictionary.






-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
ya of course, thats a trie. but sorry as before the post i didnt know the actual name. i never read data structure of a trie. i just found that there might be a tree implemented with multiple child that can perform faster searching operation and myself named that "26-ary tree" 

ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- Experienced poster
- Posts: 145
- Joined: Thu Aug 14, 2003 8:42 am
- Location: Mountain View, California
- Contact:
Re: 10999 - Crabbles
You can Goole "waterloo crabbles" to find the contest test data for this problem. However, the online judge test data is different from the waterloo data, please don't not submit their output directlyshakil wrote:I need some input and output.

Have you ever...
- Wanted to work at best companies?
- Struggled with interview problems that could be solved in 15 minutes?
- Wished you could study real-world problems?