All posts by date

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.

Given an undirected bipartite graph find a minimum cardinality vertex set which covers all edges in the sense that it contains at least one endpoint of each edge.

Given a string A (or array), and an integer k, find for every index i, the smallest index j (if it exists) such that {A[i],..,A[j-1]} consists of exact k distinct values.

Propose a data structure which permits to maintain a set of integers S, allowing to add elements and to remove the median. Both operations should work in logarithmic time.

Given a description of a landscape, describe how the rain water will drain.

Given a description of a landscape, describe how it will be flooded by the water.

Given a graph, find weights for the vertices if possible, such that there is an edge between two vertices if and only if their total weight exceeds some threshold.

You are given $n$ non intersecting line segments in the 2 dimensional plane. The segments are not parallel to the x-axis, nor to the y-axis and segments do not intersect. These segments represent roofs, and it is raining. Water flows down along the roofs, and pours from the lower endpoint to the roof below if there is one. The task is to compute how much water each roof receives.

Given $n$ rectilinear non overlapping rectangles, discovered the all connected components in their union.

Hey, if you want to improve your skills in algorithmic problem solving, you don’t even need an online judge!

The framework