Gamme pythagoricienne
En musique, on change d’octave en doublant la fréquence. On passe à la quinte en multipliant par 3/2.
Latest posts
See also all posts ordered by category or date.
Longest increasing subsequence
If we want to find the longest (strictly) increasing subsequence of an array $a$ of size $n$, of course we can assume that $dp[i]$ is the answer for the first $i$ elements and then, as a LIS of size $n$ contains a LIS of size $n - 1$:
\[dp[i] = \max_{\substack{j < i\\ a_j < a_i}} dp[j] + 1\]This gives a first algorithm in $O(n^2)$. Can we do better?
- We do not need to remember all LIS of size $\ell$. We just need to remember the smallest end for a LIS of size $\ell$, called $t[\ell]$.
- The list of smallest ends happens to be increasing (but not necessarily a subsequence). Each $t[\ell]$ forces $t[\ell - 1]$ to be lower.
In this case, we can binary search for the opt LIS to which we can add one element. This gives $O(n \log n)$. I think this is an example of Divide and Conquer DP.
I was wondering what was the $O(n \log n)$ that relies on a segment tree. A blog post on Codeforces had the answer (of course!). We need to define a new dp:
$dp[i, v]$ is the LIS using first $i$ elements finishing in $v$. Then we just need to do a min query over $dp[i, 1:v - 1]$.
(A notebook is on the way.)
Aho-Corasick
Étant donnée une liste de chaînes de caractères L, construire une structure de données qui permet en temps linéaire d’identifier toutes les occurrences des mots de L à l’intérieur d’un mot S donné.
Approximations of the Euclidean metric traveling salesman problem
Back in the good ol’ agrégation days, I remember I used as développement1 a nice 2-approx algorithm for the traveling salesman problem where the weights on the edges are given by the Euclidean distance between nodes.
-
This must mean nothing to non-French people but anyway. ↩
Count particular rectangles in a matrix
Given a matrix with distinct values, a rectangle consists of 4 cells at the intersection of two distinct rows and two distinct columns. It is good if the largest 2 values of the 4, are on the same row or the same column. Count the number of good rectangles in linear time, in the size of the matrix.
Suffix Array
Given a string s, sort all cyclic shifts of s. Formally produce a table p such that p[j]=i if s[i:]+s[:i] has rank j among all cyclic shifts.
PC Trees
A data structure representing all permutations satisfying constraints of the form: for a given set $S\subseteq\{0,1,\ldots,n-1\}$ the elements of the permutations on $\{0,1,\ldots,n-1\}$ have to be consecutive in circular manner.
Largest rectangle under an histogram
You are given an histogram and want to identify the area of the largest rectangle that fits under the histogram.
AI and LLM in education
In my new role as scientific advisor at the French Ministry of Education, I have recently been looking for meta-analyses and RCTs about impact of AI (and LLMs) in education.
Cover trees
Cover a tree with paths or caterpillars.