10999 - Crabbles

[Deno]

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

[david]

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.

[trulo17]

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

[david]

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

[Deno]

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

[wook]

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.

[cypressx]

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

[trulo17]

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.

[neno_uci]

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 

[mrahman]

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

[tywok]

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

[mrahman]

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

[little joey]

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.

[Deno]

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

[tywok]

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!