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

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

10999 - Crabbles

Post by Deno » Sun Feb 26, 2006 12:01 am

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

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

Post by david » Sun Feb 26, 2006 1:25 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.

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

Post by trulo17 » Sun Feb 26, 2006 2:11 am

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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sun Feb 26, 2006 2:20 am

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
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Sun Feb 26, 2006 3:34 am

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:

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

Post by wook » Sun Feb 26, 2006 8:29 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.. :)

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

Post by cypressx » Sun Feb 26, 2006 4:35 pm

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
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Sun Feb 26, 2006 7:50 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.

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

Post by neno_uci » Mon Feb 27, 2006 12:28 am

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
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

How to solve it <=.5s

Post by mrahman » Mon Feb 27, 2006 6:49 am

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

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

Post by tywok » Mon Feb 27, 2006 8:43 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

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Mon Feb 27, 2006 11:29 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

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

Post by little joey » Mon Feb 27, 2006 12:36 pm

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.

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

Post by Deno » Mon Feb 27, 2006 6:52 pm

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

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

Post by tywok » Mon Feb 27, 2006 8:22 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”