Once in a while I visit ACM Programming Contest Problem Set Archive. Reading and trying out a problem or two reminds me of a time when I was eligible to compete. But mainly it makes me realize how little I knew back then, and how much I still can learn. For example, as mentioned in a previous post, I only came across the Dancing Links algorithm recently which comes in handy for several contest problems.
Many problems require simple geometry algorithms. Back in the day I thought I could derive what I needed on the fly for these sorts of problems. I still believe inventing algorithms is a good thing to do, but at some point one should learn what has been done before, as it is easy to miss clever and elegant optimizations.
For example, consider the simple problem of determining which side of a line a given point lies, where the line is defined by two given points. In the past, I would have naively computed the equation for the line and substituted the point in to see which side it lies on, but now I know that it is much easier to calculate the signed area.
No comments:
Post a Comment