I completely ignored the existence of regexes when solving it. It just seemed logical to just use bitmasks. I was surprised to see so many people using regexes later.
A good C/C++ can use sscanf to the same effect as the regexes solutions. Though sscanf is a lost art that not a lot of people understand to its full power: http://forums.topcoder.com/?module=Thread&threadID=650535&start=15&mc=19#1140378 For the top scorers, array bound checking is not a critical need. If it was, you could do like me and run it with valgrind when in trouble. C++ has a lot of expressiveness, it is hard to explain. Java is ok as well, but C++ is not really a disadvantage, every language choice involves a lot of trade-offs. In C++ you can use boost and the STL, in Java you have bounds checking, yet in C++ you can make a matrix class that uses [][] syntax. Java has native hash tables that are faster than map<>. Yet C++ allows you to code a Dijkstra heap using one array + map<>. Etc, etc... On Sep 5, 7:00 am, Miguel Oliveira <[email protected]> wrote: > Jason, I did the same as you but using a bitmask instead of an > aditional [26] array. But the speedup of about a factor of 26 wasn't > an issue here. > > Ken, I have several years of experience in C++ and so I'm not thinking > in switching. I also have a few years of experience in Java but never > used the regex. When I read problem A, I thought in switching to Java > and went to the reference page of the regex expressions. However, > after a minute, i realized the solution described above which was > short, easy to code and very fast (you can check my code, username: > mogers). > > I'm not a top contestant, but for coders with this experience with the > language (the top coders probably have much more experience), "The > execution speed penalty is minmal, and the language checks for array > bounds and variable type safety should be a big help in getting a > solution coded and out the door in a minimal amount of time." this > doesn't help that much and, for me, it slows down my coding speed. > > Cheers, > Miguel > > On Sep 4, 5:01 am, Jason Lepack <[email protected]> wrote: > > > I dind't use regex, I was too worried about the complexity. My > > solution was O(N*D*L). > > > For each N I parsed the rules into a int[L][26] array, then for each > > word in D I had a boolean that determined if the word was ok or not, > > then for each letter in said word I had a boolean that checked if the > > letter was ok. If the letter wasn't ok the word wasn't. > > > Let me know if you have any questions. > > > Cheers, > > Jason > > > On Sep 3, 7:11 pm, Monang Setyawan <[email protected]> wrote: > > > > Did your solution pass the large input? I've tried similar approach first > > > but change it to the more appropriate one, since it failed the large input > > > case. > > > > On Fri, Sep 4, 2009 at 8:46 AM, Pedro Henrique Calais < > > > > [email protected]> wrote: > > > > Yes, they are available on the web site. > > > > > My solution for problem A was just to convert the words to regexs: > > > > > (ab)c(cd) --> [ab]c[cd] > > > > > and then tested the regex against all the vocabulary of the language. > > > > > -- Pedro > > > > > On Thu, Sep 3, 2009 at 10:44 PM, Dhruva Sagar > > > > <[email protected]>wrote: > > > > >> I finished only problem A for both small & large :(. > > > >> Came close to finishing B, but time ran out. > > > > >> Is it possible to see others' solutions ? I would love to. > > > > >> Thanks & Regards, > > > >> Dhruva Sagar. > > > > >> Pablo > > > >> Picasso<http://www.brainyquote.com/quotes/authors/p/pablo_picasso.html> > > > >> - "Computers are useless. They can only give you answers." > > > > >> On Fri, Sep 4, 2009 at 6:55 AM, MagicLi <[email protected]> wrote: > > > > >>> I finish problem A&B, for problem C, I finish the small input, my > > > >>> program fail the large input. I think there is better algorithm to > > > >>> work it out. > > > > -- > > > "Don't worry about what anybody else is going to do. The best way to > > > predict > > > the future is to invent it." - Alan Kay- Hide quoted text - > > > > - Show quoted text - > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
