Rencontre #9: Problèmes de l’ICPC 2021

Cette semaine, nous avons étudié une série de problèmes tirés de l’édition 2021 des phases régionales et continentales de l’ICPC en Amérique du Nord. La prochaine édition commencera le 25 février prochain. Nous constituons présentement des équipes d’étudiant.e.s qui y représenteront notre université. Si cela vous intéresse, n’hésitez pas à vous manifester! Même si vous n’estimez pas avoir beaucoup d’expérience, il reste encore du temps pour s’entraîner.

Conseils

Dans la plupart des problèmes de l’ICPC, les entrées/sorties en exemple ne sont volontairement pas représentatives de tous les cas à traiter. C’est à vous d’imaginer les cas extrêmes possibles, en lisant attentivement la description du problème. Dans le contexte du concours, c’est d’autant plus important puisque chaque soumission erronée vous coûte une pénalité de score.

Par ailleurs, dans une épreuve de l’ICPC, les problèmes ne sont pas donnés dans l’ordre de difficulté croissante. Pendant le concours, ce sera à vous d’identifier rapidement les problèmes les plus faciles, pour les traiter en premier. Chaque minute compte, puisque le temps écoulé entre le début du concours et votre résolution de chaque problème contribue à votre score.

Problèmes

Les problèmes de la série ci-dessous sont en ordre croissant de difficulté.

1. “Reversibly Cyclic Strings” — Pour une chaîne \(s\), est-ce que toutes les sous-chaînes de \(s\) apparaissent à l’envers dans au moins une des rotations de \(s\)?
2. “Tic Tac Toe Counting” — En jouant à partir d’une configuration de tic tac toe, calculez le nombre de configurations finales valides qui peuvent être atteintes.
3. “Rise and Fall” — Trouvez le plus grand entier inférieur à un entier donné dont la représentation décimale est croissante puis décroissante.
4. “Tetris Generation” — Les pièces de Tetris sont choisies en répétant des permutations aléatoires des 7 tétraminos possibles. Déterminez si une séquence de tétraminos donnée pourrait apparaître.
5. “Fail Them All!” — À partir des réponses données par des étudiants à un examen en vrai ou faux, déterminez une façon de les corriger faisant en sorte qu’aucun d’entre eux n’ait plus d’une bonne réponse.