• Algorithms
  • Throwing dice.

    Welcome back my friend! With this post I want to talk about some interesting applications of the theory of generating functions in relation to the enumeration of combinations. For this purpose let’s introduce a very simple problem: “Say we throw three regular dice, in how many ways the sum of the upper faces can be […]

  • Algorithms
  • Short post about the GCD.

    You probably think you know everything about what the Greatest Common Divisor is and how to calculate it quickly! Well, that’s most probably the case, but just in case you do not remember all the details then here’s a short post about the GCD! (All the code is available here) Simple GCD Let’s start with the basic […]

  • Algorithms
  • Stern-Brocot tree’s.

    I’ve encountered this mirable structure this weekend when dealing with cleaver ways to represent fraction of rational numbers n/m where gcd(n,m)=1 (nominator and denominator are relatively prime), Stern-Brocot tree’s are just all about building all the possible fractions that are in they lowest form. What’s interesting (but that came as evident once one understand this structure) is […]

  • Algorithms
  • Segment tree

    What is the best thing you may possible do when having a eight hours train trip? Writing a blog post of course! That’s actually an interesting story by itself: Where I was and why it take that long to come back home! Anyway! Let’s say you’ve an array of integers, as usual from index 0 to […]

  • Algorithms
  • Solution space.

    Certain problems required us to try all the possible solutions to find the one that best fit the given constraint, a very popular brute force way is to perform a complete search of the solution space by iterating over and over the data and changing each time the input variables. If the problem require to […]

  • Algorithms
  • Suffix trees.

    An entire post covering both the theoretical part and the implementation is going to take too long, for this reason I’m splitting the material in two parts: A post with some theory introduction, and one post which will be focused on implementation details. The algorithm I would like to show you is the Ukkonen method for […]

  • Algorithms
  • Subsequences and Fenwick tree’s

    Let’s say that we have a sequence A of 1<=n<=10^5 elements, and that this sequence may or may not be ordered but all the numbers {1…n} are present exactly once. And now given 1<=k<=10, you’re asked to find all the increasing sub-sequences of A with exactly k+1 elements. This is a problem I get from a competitive programming […]