10999 - Crabbles

[little joey]

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.

[Deno]

Thank you...but I don't understand what you mean by "This kind of data structures are those that just don't type and debug during a contest instead of using a previously written and tested code."

Do you mean he coded and tested it in advance so he doesn't need to debug?

Thanks

[wook]

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 ?

[Larry]

You can encode strings into numbers, if you looked at the constraint enough..

[mf]

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)

[Per]

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 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.

[C]

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.

[ayon]

algorithm - backtracking(of course with proper pruning)
data structure - 26-ary tree
time - 0.258 sec
memory - 12544KB
ranklist - 3rd(currently)

[shanto86]

will u plz tell mne what is 26-ary tree? is it similar as binary tree jast having 26 edges at each node? if so then isnt it a trie?

[ayon]

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"

[shakil]

I need some input and output.

[DD]

I need some input and output.

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 directly