Sebastian Mestre's Algorithmic Adventures

Background: Fenwick Tree The Fenwick tree is a data structure that is commonly used to perform prefix sum queries and point updates on some array A. Leaving the issue of updates aside the general idea is that, for each index i, it stores the sum of A over the range (i−f(i),i] (yes, that's an open-closed interval), where f(i) returns the least significant bit of i. To compute a prefix sum over [1,i1] we start with the interval (i2,i1] (where i2=i1−f(i1)), then we add (i3,i2] (where i3=i2−f(i2)), and so on until we cover the entire range. Since each i[k+1] has one fewer bit than i[k], this can only happen O(log(i1)) times in the worst case. Therefore any prefix sum query is computed in O(logn) worst case running time. int fenwick_tree[MAXN]; int prefix(int i) { int x = 0; for (; i > 0; i -= f(i)) x += fenwick_tree[i]; return x; } It is also easy to compute any range sum query over a range [l,r] by taking the sum over the prefix [1,r] and subtracting [1,l−1]. int

Part 1: expressions, arithmetic Part 2: statements, control flow Ever since I was a teenager I wanted to create my own systems programming language. Such a programming language would certainly have to be compiled to native code, which meant I'd have to write a compiler. Even though I managed to write several half-working parsers, I'd always fail at the stage of generating assembly code, as the task turned too complex. In this blog I intend to show my teenage self how writing a code generator is, in fact, not complex at all, and it can be fully done in a couple of weekends. (As long as we make some simplifying assumptions) I will that assume you already know that representing programs within a program is surprisingly easy Where do we even start? The goal today is to translate a high level language to x86-64 machine code. Our high-level language will have integer literals, variables, negation, and addition. To make our job simpler, we will translate the hig

Suppose that you want to create a brand new programming language that will change the world. Or that you want to auto-formatter that gets indentation just right . Or maybe you want to write a pre-processor for an existing language, to hack some missing feature into it . Whatever it may be, there are many reasons to write programs that manipulate other programs as data and the first step is to figure out how you are going to represent that data within the program. My goal in this article is to explain one of the most standard approaches (Abstract Syntax Trees) and show how they are actually really easy to understand and implement. This article has many code examples in the C language. What kind of language are we defining? Let's start with a simple example: a language with variables, numbers, and addition. Note that this language does not have statements, but only expressions that evaluate to simple values. This means that we will be able to represent expressions such as

Problem Suppose we have two arrays a[1], a[2], ..., a[n] and b[1], b[2], ..., b[m] , and a predicate P(a, b) . For each index i (1 ≤ i ≤ n) we want to find the least j (1 ≤ j ≤ m) such that P(a[i], b[j]) is true. Naive Solution With the information we have, we can't do much. The optimal solution given what we know so far is: Iterate over every i, then over every j, until we find a match. fn search(i) { solution[i] = m+ 1 for j in 1 . .m { if P( a [i], b [j]) { solution[i] = j break } } } for i in 1 . .n { search(i) } This is O(n * m). Additional constraints Let's introduce a construct that will lead to a faster solution. Consider this definition: P'(a, B) = { true if there is some b in B such that P(a, b) { false otherwise Let's say we can evaluate P' in O(1), given some O(|B|) precomputation. Then, an alternative strategy becomes available. Solution For each i, use bi

Estaba hablando con un amigo y me preguntó sobre el uso de FFT en programación competitiva. El texto de abajo surgió en esa conversación. Fourier La clave es que hay muchos problemas que se pueden resolver usando esta función: // tenemos dos bolsas A y B con bolitas con números naturales // queremos saber qué numeros se pueden formar tomando una bolita de A y una de B y sumando sus numeros // // a[i] es la cantidad de bolitas con el numero i en A // b[j] es la cantidad de bolitas con el numero j en B vector combinaciones(vector a, vector b) { int n = a.size(), m = b.size(); vector c(n+m-1); forn(i,n) forn(j,m) c[i+j] += a[i] * b[j]; return c; } Por otro lado, consideramos el producto de polinomios // producto de polinomios A y B // a[i] es el coeficiente de grado i de A // b[j] es el coeficiente de grado j de B vector producto_polinomio(vector a, vector b) { int n = a.size(), m = b.size(); vector c(n+m-1); forn(i,n) forn(j,m) c[i+j] += a[

Un amigo tenía algunas dudas sobre perfect forwarding en C++, y terminé escribiendo esta explicación. value categories Antes de hablar sobre los detalles de la deduccion de tipos en C++ es fundamental mencionar las value categories. En C++ hay dos tipos de referencias. Referencias a lvalues y referencias a rvalues. Llamemoslas L-refs y R-refs, respectivamente. Normalmente, las L-refs apuntan a objetos que tienen una ubicación fija en memoria, mientras que las R-refs apuntan a objetos temporales. Normalmente, una L-ref se denota T& y una R-ref se denota T&& , donde T es un tipo concreto. Por convención, si recibís una R-ref, tenes derecho a romper el objeto al que apunta. En caso contrario, no. std::move toma una L-ref y la castea a R-ref. template argument deduction Digamos que tenemos una funcion monki , que tiene un template parameter T . Y digamos que T aparece dentro del tipo de uno de los parametros de monki . Por ejemplo: template<typename T>