Page 2 of 2

Posted: Mon Feb 27, 2006 9:01 pm
by 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.

Posted: Mon Feb 27, 2006 9:07 pm
by 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

Posted: Tue Feb 28, 2006 5:20 am
by 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 ?

Posted: Wed Mar 01, 2006 2:24 am
by Larry
You can encode strings into numbers, if you looked at the constraint enough..

Posted: Wed Mar 01, 2006 3:07 am
by 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)

Posted: Wed Mar 01, 2006 10:18 am
by Per
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 ?
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.

Posted: Thu Apr 27, 2006 2:53 pm
by 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 :P . 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. :P :P :P :P

Posted: Mon May 15, 2006 10:40 pm
by ayon
algorithm - backtracking(of course with proper pruning)
data structure - 26-ary tree
time - 0.258 sec
memory - 12544KB :(
ranklist - 3rd(currently) :)

Posted: Thu Jun 01, 2006 11:01 am
by 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?

Posted: Thu Jun 01, 2006 10:20 pm
by 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" :oops:

input and output

Posted: Fri Jun 29, 2007 6:32 am
by shakil
I need some input and output.

Re: 10999 - Crabbles

Posted: Fri Apr 08, 2011 6:32 am
by DD
shakil wrote: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 :lol: