Nicolas Thiébaud home

Google Code Jam 2012 – Qualification Round

Le 15 avril 2012 – Paris

Le Google Code Jam est une compétition d’algorithmique qui réunit des hackers du monde entier. Ce weekend plus de 20000 personnes ont tenté de se qualifier et 16000 d’entre elles ont réussit.

Voici une courte explication des solutions qui m’ont permies de me qualifier.

A. Speaking in Tongues

Ce problème était franchement très facile, il fallait simplement lire attentivement l’énoncé. Je ne m’attarde donc pas dessus, vous pouvez lire mon input ici

B. Dancing With the Googlers

Un ensemble de danseurs est noté par un jury composé de trois personnes. Les jurés sont très homogène dans leur notation, et lorsque deux notes diffèrent de deux points, la note globale est considérée surprenante. Le jury ne diffère jamais de plus de deux points.
Etant donné les notes totale ti des N danseurs, ainsi que le nombre S de note surprenante, quel est le nombre maximum de danseurs à avoir une note individuelle >= p. (énoncé complet)

L’énoncé devait faire penser à une solution de type greedy, notament parce que l’on cherche un extremum.

Les danseurs ayant pu avoir une note supérieure à p sont ceux ayant une note ti >= 3*p - 2: ils forcément obtenu une note >= p sans qu’elle soit qualifiée de surprenante ainsi que ceux ayant une note surprenante ti >= 3*p - 4.

Pour simplifier l’implémentation, ont peut donc chercher les candidat dans le tableau des notes triées par ordre décroissant, tout en veillant aux cas p=1 ou p=0.

Voici ma solution:

C. Recycled Numbers

Etant donné deux entiers A et B, nous cherchons l’ensemble des couples (n, m) tels que A <= n < m <= B avec m pouvant être obtenu par permutation circulaire des chiffres qui composent n. Par exemple 12345 et 34512, ou 6307 et 7630.

Ma première implémentation se réalisait en temps quadratique: j’itérait sur les indices n et m ce qui n’était pas tolérable lorsque A et B était d’un ordre supérieur à 10 4. La solution consistait à n’utiliser qu’un seul indice de A à B et de générer l’ensemble des permutations pour cet indice et de ne retenir que celles qui satisfont les conditions précédentes.

Voici l’ensemble des couples (n, m) compris entre 1111 et 2222:

Et ma solution:

D. Mirrors

Le dernier problème était nettement plus dur: un homme est placé dans une pièce dont les murs sont recouverts de mirroirs. Etant donné la forme de la pièce ainsi que la position de l’homme, combien d’images de lui même peut-il voir ?

J’ai trouvé le bon algorithme pour ce problème (solution officielle), mais n’ai pas réussit à obtenir une implémentation satifaisante. Je reprendrai peut-être ce code pour le terminer.