Maintain a numerical table tab that implements the following operations in logarithmic time: for a range of table indices, query the maximum value, query the minimum value, query the sum, set all entries of that range to some value, add some value to all entries of that range.

Nous décrivons ici des solutions pour la ronde 1B du concours Google Codejam 2017.

Pourrez-vous résoudre cette énigme du jeu Le Compte est bon ?

Nous décrivons ici notre petite expérience avec le concours Google Hashcode 2017 : Optimize Cache Servers for YouTube.

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