Contexte

Bonjour.

Le concours annuel Google Hashcode consiste à résoudre en équipe une instance d’un problème NP-complet. Résoudre veut dire ici produire une solution faisable. La valeur objectif atteinte est le score de la solution. Les problèmes présentés sont assez purs, comparés à ceux du concours annuel Roadef challenge, qui contiennent beaucoup plus de contraintes et sont plus proches d’un problème réel.

Pour commencer l’année, ce week-end de l’épiphanie ont eu lieu les qualifications de Facebook Hacker Cup.

Contexte

Note : Une partie de cet article a été reprise d’ici, mais pas de panique, je suis une co-auteure.

Contexte

Merkle trees (1979)

Le principe est simple : calculer le hash d’un nœud à partir d’un hash de ses fils. Dans un arbre binaire, pour un nœud ayant pour fils $h_1$ et $h_2$ : \(h(noeud) = h(h1, h2)\).

Given a grid containing some segments, find the minimum number of times segments need to be displaced such that a particular segment can escape from the grid.

Given a boolean formula consisting of Horn clauses, set a minimal number of variables to True in order to satisfy all clauses.

Given a 2 player impartial game, decide for a given configuration if there is a possibility for the first player to win assuming the second player plays perfectly.

Le saviez-vous ? Du 19 au 20 novembre 2016 ont eu lieu les épreuves régionales SWERC du concours de programmation ACM/ICPC à Porto, au Portugal.

• 11 problèmes
• 5 heures
• 3 personnes et 1 clavier par équipe

Et voici les photos de SWERC 2015.

Did you know? SWERC 2016 was held in Porto (Portugal) on November 19–20th. It stands for: the SouthWestern European Regional Contest of the ACM ICPC (International Collegiate Programming Contest).

• 11 problems
• 5 hours
• 3 people and 1 keyboard per team

Jussieu, room 26-25/105, from 9:00-12:00 only the ecole polytechnique teams, from 13:00-18:00 (+discussions) open to everyone.

Given a table, find for every entry how many elements there are to left that are larger and how many elements there are to right that are smaller. In other words find out how many swaps bubble sort will do on the table.

Find a shortest cycle in a given undirected graph.

You are given n pairs of time intervals. From each pair select exactly one such that the selected time intervals do not intersect.

Jussieu, room 26-25/105, 14:00 until 17:00

Jussieu, room 26-25/105, 14:00 until 17:00