All posts by date

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

Maintain a set, allowing to add or remove elements and to query the sum of the up to k largest items.

Maintain a set, allowing to add or remove elements and to query the smallest element.

Parcours en profondeur de Trémaux

Maintain a matrix in a datastructure, allowing to update entries and to query the sum of a rectangular submatrix in time $O(\log(n)\log(m))$, where $n,m$ are the dimensions of the matrix.

Given a string $s$, determine the number of distinct substrings that it contains.

Given the a rewriting system of the form $f:\Sigma\rightarrow \Sigma^\star$, determine the limit of $f^i(a)$ for some given seed letter $a\in \Sigma$.

Étant donné n on veut produire en temps linéaire deux tableaux factor et primes, tel que primes contienne tous les nombres premiers entre 2 et n, et que factor[x] contienne le plus petit facteur de x, avec facteur[x]==x si x est premier.

Given the grammar of a context free language and a string, decide if the string can be generated by the grammar.

Given directed graph with possibly negative edge weights, find a shortest path between two given vertices.