# All posts by date

## Meilleur developpeur de France 2023

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.

## SWERC 2022 Practice Session - Bloggers

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

## Deep Reinforcement Learning

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

## AlphaGo and Alpha Zero

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

## Six dates importantes en algorithmique

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

## Quadrangle Inequality trick for dynamic programs

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

## Pareto optimality

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

## Multiplying polynomials

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.

## Making pairs adjacent at minimal cost

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.

## Identifying the maximum in a sliding window

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

## Maintaining sum of k largest items in a dynamic set

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

## Heap allowing to remove items

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

## Query the sum of a submatrix

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.

## Count all distinct substrings

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

## Determine the fixpoint of a rewriting system

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

## Comment décomposer un nombre en facteurs premiers ?

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

## Recognize a context free language

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

## Shortest path with negative edge weights

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