I haven't implemented this myself (thought of it over dinner), but reducing the search space using the fact that permuting digits doesn't affect the happiness of a number could reduce the runtime over the "check each number in sequence, in each base" approach that I used.
i.e. if we consider up to 9 digit numbers (in base ten), there are 18 choose 9 < 50000 possibilities for their digit sequences when put in sorted order. Generate these and isolate the happy ones (I don't know how many there are), and you can now generate the base 10 happy numbers with some kind of priority queue. The same kind of idea applies to the other bases; even though the number of digits increase, the decrease in the number of digit values has a greater effect (the numbers of digit combinations I calculate are [31,210,816,2380,6188,12376,19448,43758,48620] for bases [2..10]; though all base-2 numbers are happy so maybe just leave those out). Then we can do a mergesort-like intersection to find the first common happy number. Not having tested this, I'm not sure if the overhead in this approach makes it worthwhile -- but it's the best I could think of so far. On Sep 12, 12:34 am, Bartholomew Furrow <fur...@gmail.com> wrote: > Sometimes solutions run near the limit, and it can help to have fast > hardware; I'd like to think this is the exception rather than the rule. > With that said, it's a shame when it does happen. I'm hoping you can think > of an optimization or two that would have brought the runtime down by some > constant factor, so that you could have done it even with 2x slower > hardware. > Incidentally, an alternative was to do precomputation. I didn't work on > that problem myself, but I think it was a way around doing a lot of > computation during the 8 minutes. > > Also it was apparently solvable within 20 seconds in C++, though as I > mentioned I don't know how. :-) Terence, would you mind linking your > solution? > > Bartholomew > > > > On Fri, Sep 11, 2009 at 11:00 PM, cyberfish <cyberf...@wecheer.com> wrote: > > > Just thought I should point out that, for the large input of question > > A (round 1A), my program solved it in a little under 7 minutes on my > > computer (a Core 2 Duo overclocked to 3.3ghz). A slower computer may > > not have made it, so I think this gives an unfair advantage to people > > with fast computers (like myself) :).- 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 google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
