Skip to content

Month: December 2016

My favorite bug

It was early November 2013, and me and a friend of mine, Helgi, were preparing to compete in our annual ACM-ICPC regional contest. We had been adding various algorithms and data structures to our code library, which we were allowed to bring with us to the contest. He had recently taken an Operating Systems course, where he had implemented a Skip list for use in a memory allocator. To my knowledge, Skip lists have not been used much in programming contests, but since it is a relatively simple (to code) data structure that supports the same operations as balanced binary search trees with the same (expected) time complexity, we thought it might be a good idea to add it to our library. (Note that C++, which was our programming language of choice, already provides a balanced binary search tree through its standard library, but it doesn’t support augmentation, which is something that is frequently needed in programming contests.)