Thanks, Matteo for that tip. Bjoern, fantastic that you are working on improving in this respect - it will come in very handy not just in programming contests but also in real life systems where the efficiency of your approach can drastically affect the scalability of what you build.
Carlos is right, this can basically be described as dynamic programming, and it is not uncommon to see algorithms like these in programming contests. It is probably possible to classify most programming contest problems into several different classes, like searching, sorting, permutations, etc.. so it helps to be familiar with how to implement an efficient solution for each different basic type of problem. But I think perhaps the most important part is trying to keep your mind open to different approaches to solving a problem, as it is very easy for our brains to get stuck viewing the problem in a certain way once we have a possible solution in our mind. Especially in these cases where the larger data sets are designed to overwhelm inefficient algorithms, looking at the big-O() of your solution lets you see where it might not scale up well, and then try to identify different ways to tackle the inefficiencies. When your algorithm grows in complexity too quickly, you can often find something in the problem which your current approach did not take advantage of - redundency, discarded or unused information, additional relationships such as symmetries, etc. Then you may be able to find a more efficient way that makes use of that - e.g. dynamic programming can often be thought of as recursion without discarding/re-calculating your repeated intermediate results. Hope this helps, and good luck in the next round! On Sep 5, 12:05 pm, Carlos Guia <[email protected]> wrote: > Search for Dynamic Programming (DP) and his close cousin memoization (not a > typo). > A very high percent of programming contests have at least one DP problem, so > getting familiar with it will certainly help you improve in this type of > competitions. > You can check the tutorials > athttp://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index > And you can also look for the books "*Art of Programming Contest" and > "Programming > Challenges".* > > There you will find information on DP and some other very common algorithms > for programming contests. > > Carlos Guía > > > > On Sat, Sep 5, 2009 at 8:42 AM, Bjoern <[email protected]> wrote: > > > Thanks! > > > Just wondering, how did you arrive at the solution? In hindsight it > > seems obvious, but I must admit I did not think of it during the > > competition :-) Certainly I don't see a way to think of it in 10 > > minutes or so. > > > So I wonder if similar algorithms have come up in other programming > > competitions, or if the approach in general is well known (what are > > other use cases)? > > > Just wondering how to improve my skills for the next round/future > > competitions.- 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 -~----------~----~----~----~------~----~------~--~---
