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$:
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]$.
É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é.
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. ↩
• combinatorics • Christoph Dürr, Pavel Kunyavskiy, Aris Pagourtzis
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.
• data structures • Rami Benelmir, Christoph Dürr, Erisa Kohansal and Yanni Lefki
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.
• artificial intelligencelarge language models • Jill-Jênn Vie
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.
Le 9 mars 2023 avait lieu la compétition Meilleur Développeur de France 2023. Les algorithmes nécessaires sont résoudre les problèmes sont assez simples, mais il faut coder rapidement. Après coup, et à tête reposée, voici comment on aurait pu résoudre certains des problèmes.