Page 1 of 2

10999 - Crabbles

Posted: Sun Feb 26, 2006 12:01 am
by 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. :cry: )

Thank you

Posted: Sun Feb 26, 2006 1:25 am
by 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.

Posted: Sun Feb 26, 2006 2:11 am
by 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

Posted: Sun Feb 26, 2006 2:20 am
by 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).

Posted: Sun Feb 26, 2006 3:34 am
by Deno
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... :cry:

Posted: Sun Feb 26, 2006 8:29 am
by 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.

Posted: Sun Feb 26, 2006 4:35 pm
by 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 ;-)

Posted: Sun Feb 26, 2006 7:50 pm
by 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.

Posted: Mon Feb 27, 2006 12:28 am
by 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 

How to solve it <=.5s

Posted: Mon Feb 27, 2006 6:49 am
by 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

Posted: Mon Feb 27, 2006 8:43 am
by 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...

Posted: Mon Feb 27, 2006 11:29 am
by 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

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

Posted: Mon Feb 27, 2006 6:52 pm
by Deno
To little joey:
how did you store those strings? hos did you lookup the dictionary?
You wrote a hash table during the contest? :o

Thank you

Posted: Mon Feb 27, 2006 8:22 pm
by 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!