All posts by date

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]$.

(A notebook is on the way.)

É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éveloppement¹ a nice 2-approx algorithm for the traveling salesman problem where the weights on the edges are given by the Euclidean distance between nodes.

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.

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.

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.

You are given an histogram and want to identify the area of the largest rectangle that fits under the histogram.

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 a tree with paths or caterpillars.

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.

Abstract: Maintain two tables $t_0$, $t_1$. Updates: given $i,j,c$ increment $t_c$ between indices $i$ and $j$. After every update output $\sum_k \max{t_0[k],t_1[k]}$.

Stable Baselines rely on TF 1.x but Stable Baselines v3 rely on PyTorch.

SPOJ

In December 2016 we presented it at ENS Paris-Saclay with Étienne Simon but apparently I never wrote a blog post in the end.

-300

Algorithme d’Euclide (qui date peut-être de l’école de Pythagore 530 av. J.C.)

Application: Given an ordered list of keys with frequencies, build a binary search tree on those keys which minimizes the average query cost.

Compute the pareto set of a given set of points in 2 or 3 dimensions.

You are given two polynomials $P$ and $Q$ and want to compute their product. The polynomials are given in form of an array with their coefficients.

You are given an array $X$ with the promise that each of its values appears exactly twice. You want to transform $X$ such that at the end all pairs are adjacent in the array. An allowed operation consists in removing a value from $X$ and appending it at the end. The cost of a solution is the maximal value which was moved.

Given an array $x$ and an integer $k$, determine for every index $1 \leq j\leq n$ the maximum $x[i]$ among all indices $\max\{1,j-k+1 \} \leq i \leq j$.