10999 - Crabbles

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

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Feb 27, 2006 9:01 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.

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Mon Feb 27, 2006 9:07 pm

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
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Tue Feb 28, 2006 5:20 am

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 ?
Sorry For My Poor English.. :)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Mar 01, 2006 2:24 am

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Mar 01, 2006 3:07 am

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Mar 01, 2006 10:18 am

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.

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » Thu Apr 27, 2006 2:53 pm

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

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon May 15, 2006 10:40 pm

algorithm - backtracking(of course with proper pruning)
data structure - 26-ary tree
time - 0.258 sec
memory - 12544KB :(
ranklist - 3rd(currently) :)
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Thu Jun 01, 2006 11:01 am

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?
Self judging is the best judging!

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Jun 01, 2006 10:20 pm

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:
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

input and output

Post by shakil » Fri Jun 29, 2007 6:32 am

I need some input and output.
SHAKIL

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10999 - Crabbles

Post by DD » Fri Apr 08, 2011 6:32 am

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:
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?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 109 (10900-10999)”