## 10999 - Crabbles

Moderator: Board moderators

### 10999 - Crabbles

How do people solve this question so that the program runs within 10 seconds?

(I even saw some people's programs that ran within 2 seconds during the contest. )

Thank you
Deno
New poster

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

There are many fewer words that can be formed with the given letters (2^10, ignoring letter order) than there are words in the dictionary, and for each word that can be formed you can check efficiently whether it is in the dictionary or not.
david
Learning poster

Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

i got acc in this one just within time( 8.443 seconds) so i would like to know a better way to do this task.What i'm doing is to see for every word in dictionary if it can be formed with the p letters. You say we can consider just 2^p words and look for them in dictionary but,shouldn't we consider every permutation of this 2^p words? Could you explain a little more please? thx in advance
trulo17
Learning poster

Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

You say we can consider just 2^p words and look for them in dictionary but,shouldn't we consider every permutation of this 2^p words?

No, why should we? If we have the letters a, c, a, d, we can build the words acad, cada, aadc..., regardless of the letter order within a word. So if the dictionary contains the word cada, we simply record it as aacd (that is, we sort the word).
david
Learning poster

Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

trulo17 wrote:i got acc in this one just within time( 8.443 seconds) so i would like to know a better way to do this task.What i'm doing is to see for every word in dictionary if it can be formed with the p letters.

This is similar to what I did...but I got TLE...
Deno
New poster

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

Can anybody give me some tricky inputs?

I think my algorithm is not too slow;
It gave me "1.4 sec WA".

maybe.. O(NlgN * 10 + M(2^p + p * (2^p) * 10 + 2^p * lgN * 10)),
where the constant 10 comes from comparing strings.
Sorry For My Poor English..
wook
Learning poster

Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Isn't there a trickier and faster way to solve this problem ? Cause this seems too much brute force to me , is this the way to solve this kind of problems ? Thank you in advance !

P.S. I just was hoping for something really clever
cypressx
New poster

Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

finally got david idea and got ac in 3.787, which i think is good enough considering i'm using string and some stl.
To Deno: maybe you are using string too, at contest i used string and got tle, switching to char[] and doing some prunning( i didn't consider words with length>p) is how i got my first idea accepted.
trulo17
Learning poster

Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

I am getting WA with my code, could someone give me test cases or at least a counterexample?, 10x in advance,

Yandry.

Code: Select all
`cut after i found my silly mistake `
neno_uci
Experienced poster

Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### How to solve it <=.5s

I have accepted It with 1.008s. I don't understand how Colin McCambridge solve it 0.002s(Look like a Mathematical Problem solution). And even I can't guess any Idea How to reduce my runtime less than 0.500s.
Thank you
Practice Makes a man perfect
mrahman
New poster

Posts: 25
Joined: Mon Oct 24, 2005 9:45 am

the judge input&output is somewhere on waterloo's server, that's why he got 0.002s. I really wonder if you can read 100000 words in 0.002s...
Impossible is nothing
tywok
New poster

Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Thank you tywok. When I see 64 in Memory Column, I think thats too. Will STL reduce my Running time or Little Joye use any other special algorithm. Thanks in advance
Practice Makes a man perfect
mrahman
New poster

Posts: 25
Joined: Mon Oct 24, 2005 9:45 am

My code is in C, not C++, so I don't use STL. Using STL you can substancially reduce the size of your code (and therefor coding time), but, as is discussed on these boards before, the judge doesn't use some nescessary compiler options so execution speed is lower than possible.
I don't know what you mean by 'special algorithm'. My dictionary lookup is (almost) O(1) per query, but there is nothing special about it. Also the dictionary entries are not stored as strings, which you could call 'special'. I don't use special hacks to speed up, just plain C code. I think a time below 0.1 seconds is possible for this problem.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

To little joey:
how did you store those strings? hos did you lookup the dictionary?
You wrote a hash table during the contest?

Thank you
Deno
New poster

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

I would say he uses a trie: http://en.wikipedia.org/wiki/Trie

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. Try to do it yourself and you could be much faster nextime!
Impossible is nothing
tywok
New poster

Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Next