Skip to main content Link Search Menu Expand Document (external link)

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.

Organizing contests with judges

SPOJ

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.

Parcours en profondeur de Trémaux, parcours main gauche de Pledge

Parcours en profondeur de Trémaux

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.