I know, I coded in Ruby, it can't compare in time complexity with C++.I just don't know C++ that well. Coding is easier in something like Ruby / Java.
Thanks & Regards, Dhruva Sagar. Samuel Goldwyn<http://www.brainyquote.com/quotes/authors/s/samuel_goldwyn.html> - "I'm willing to admit that I may not always be right, but I am never wrong." On Fri, Sep 4, 2009 at 4:00 PM, Miguel Oliveira < [email protected]> wrote: > > I used C++. It's my "default" programming language :) > > The first 22 lines of the source code are just a template. > > On Sep 4, 12:01 pm, Dhruva Sagar <[email protected]> wrote: > > Which programming language did you code in, I will surely check your code > i > > time. > > Thanks & Regards, > > Dhruva Sagar. > > > > Jonathan Swift< > http://www.brainyquote.com/quotes/authors/j/jonathan_swift.html> > > - "May you live every day of your life." > > > > On Fri, Sep 4, 2009 at 3:11 PM, Miguel Oliveira < > > > > [email protected]> wrote: > > > > > For problem A, I converted both the dictionary and the patterns to a > > > list of L bitmasks (one for each letter/position in the pattern). Each > > > bitmask has the bit i with 1 if the letter 'a'+i belongs to the word > > > or to the pattern in that position. Then, you just have to do at most > > > L bitwise "AND" operations per comparison. This solutions runs in ~0 > > > secs. > > > > > For B, I did a kind of Flood Fill (http://en.wikipedia.org/wiki/ > > > Flood_fill), running from top to bottom, left to right. > > > > > For C, I did the easiest Dynamic Programming (http://en.wikipedia.org/ > > > wiki/Dynamic_programming) approach. But it's easy to optimize it (it > > > still runs in about 0.1 secs). > > > > > You may check my code. My username is mogers. > > > > > I think that the problems were easier than last year's qualification > > > round. Too bad because I could solve problems like these in the online > > > round 1 x) > > > > > On Sep 4, 9:53 am, Monang Setyawan <[email protected]> wrote: > > > > There is contest analysis in the dashboard. > > > > > > On Fri, Sep 4, 2009 at 2:50 PM, Dhruva Sagar <[email protected] > > > > > wrote: > > > > > But I don't see how I could improve my algo. > > > > > Thanks & Regards, > > > > > Dhruva Sagar. > > > > > > > Mike Ditka < > > >http://www.brainyquote.com/quotes/authors/m/mike_ditka.html> - "If God > had > > > wanted man to play soccer, he wouldn't have given us arms." > > > > > > > On Fri, Sep 4, 2009 at 1:18 PM, Monang Setyawan <[email protected]> > > > wrote: > > > > > > >> I think the algorithm have more impact than language choice, at > least > > > in > > > > >> contest like this one. > > > > > > >> On Fri, Sep 4, 2009 at 2:42 PM, Dhruva Sagar < > [email protected] > > > >wrote: > > > > > > >>> For the large input, my solution did take long, but it was lesser > > > than a > > > > >>> minute in my knowledge. The best solutions are almost always in > C/C++ > > > > > > >>> Thanks & Regards, > > > > >>> Dhruva Sagar. > > > > > > >>> Stephen Leacock< > > >http://www.brainyquote.com/quotes/authors/s/stephen_leacock.html> - "I > > > detest life-insurance agents: they always argue that I shall some day > > > > >>> die, which is not so." > > > > > > >>> On Fri, Sep 4, 2009 at 12:49 PM, Monang Setyawan < > [email protected] > > > >wrote: > > > > > > >>>> Well, I've run my old code again (which use regex) and run > against > > > some > > > > >>>> generated large input. It took more than a minute to complete > > > (that's why I > > > > >>>> consider it "failed"). The better solution run under 1 second > > > against the > > > > >>>> same input. > > > > > > >>>> On Fri, Sep 4, 2009 at 9:18 AM, Dhruva Sagar < > > > [email protected]>wrote: > > > > > > >>>>> Yes apparently my solution solved the large input file as well. > > > > >>>>> I don't see why it shouldn't. > > > > > > >>>>> This is my solution in Ruby : (easiest programming language to > > > > >>>>> understand IMO) > > > > > > >>>>> filename = ARGV[0] > > > > >>>>> input = IO.readlines(filename) > > > > >>>>> output = File.new('output', 'w') > > > > > > >>>>> L = input[0].split(' ')[0].to_i > > > > >>>>> D = input[0].split(' ')[1].to_i > > > > >>>>> N = input[0].split(' ')[2].to_i > > > > > > >>>>> words = [] > > > > >>>>> testcases = [] > > > > > > >>>>> 1.upto(D) do |i| > > > > >>>>> words[i-1] = input[i] > > > > >>>>> end > > > > > > >>>>> (D+1).upto(D+N) do |i| > > > > >>>>> testcases[i-D-1] = input[i] > > > > >>>>> testcases[i-D-1] = > testcases[i-D-1].gsub('(','[').gsub(')',']') > > > > >>>>> end > > > > > > >>>>> testcases.each_with_index do |t, i| > > > > >>>>> r = Regexp.new(t.to_s) > > > > >>>>> count = 0 > > > > >>>>> words.each do |w| > > > > >>>>> count+=1 if !r.match(w).nil? > > > > >>>>> end > > > > >>>>> output.puts "Case ##{i+1}: #{count}\n" > > > > >>>>> end > > > > > > >>>>> output.close > > > > > > >>>>> Thanks & Regards, > > > > >>>>> Dhruva Sagar. > > > > > > >>>>> Charles de Gaulle< > > >http://www.brainyquote.com/quotes/authors/c/charles_de_gaulle.html> - > "The > > > better I get to know men, the more I find myself loving dogs." > > > > > > >>>>> On Fri, Sep 4, 2009 at 7:41 AM, 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 > > > > > > >>>> -- > > > > >>>> "Don't worry about what anybody else is going to do. The best > way to > > > > >>>> predict the future is to invent it." - Alan Kay > > > > > > >> -- > > > > >> "Don't worry about what anybody else is going to do. The best way > to > > > > >> predict the future is to invent it." - Alan Kay > > > > > > -- > > > > "Don't worry about what anybody else is going to do. The best way to > > > predict > > > > the future is to invent it." - Alan Kay > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
