Le premier juin, les finales de notre championnat de programmation ont eu lieu. Les noms des gagnants sont déjà connus. Bientôt, ils recevront leurs récompenses, et en attendant, nous commençons à publier une analyse des tâches du championnat. Dans un premier temps, nous analyserons les tâches de la phase de qualification chez les développeurs backend.
La qualification dure une semaine, et le nombre de participants se compte par milliers, donc il s'avère que la préparation des tâches n'est pas une tâche facile. Au total, nous avons dû effectuer 24 tâches et les répartir entre les quatre options afin que les options soient comparables en complexité.
Cette fois, nous avons proposé six tâches, pour chacune desquelles il a été possible de proposer plusieurs formulations alternatives: une tâche inventée a donné lieu à quatre à la fois! Ainsi, les options se sont avérées comparables autant que possible.
Par conséquent, je ne publierai pas d'analyses des 24 problèmes. Au lieu de cela, j'analyserai six tâches de l'une des options de qualification: d'autres sont résolues de manière similaire.
A. Alarmes
Condition de tâcheTravailler dans la plupart des entreprises informatiques présente de nombreux avantages: il n'y a pas de code vestimentaire, vous pouvez parfois travailler à distance, avec des collègues sympas et intelligents, et, bien sûr, un horaire gratuit! Cependant, un horaire libre et la possibilité de travailler à distance nécessitent beaucoup de volonté.
Le programmeur Alexei aime travailler la nuit et n'aime pas venir travailler tard. Pour se réveiller précisément le matin, Alexey démarre tous les soirs N alarmes sur votre téléphone. Chaque réveil est configuré pour sonner tous les X minutes à partir du moment où il a apporté. Par exemple, si une alarme a été définie à un moment donné ti puis il appellera parfois ti , ti+X , ti+2 cdotX etc. En même temps, si deux alarmes commencent à sonner à un moment donné, une seule d'entre elles s'affiche.
On sait qu'avant de se réveiller, Alexey écoute tous les matins K réveils, après quoi il se réveille. Déterminez le moment où Alex se réveille.
Toutes les alarmes sonnent à des heures entières et toutes les alarmes ont la même période de répétition d'appel. Si deux alarmes sont définies à des moments précis ti et tj , et ces points dans le temps donnent le même reste lorsqu'ils sont divisés par X , vous ne pouvez laisser qu'un seul réveil - celui qui sonne le premier.
La première étape consiste donc à se débarrasser des alarmes inutiles: nous allons les regrouper par valeur du reste de la division par X et de chaque groupe, nous ne laisserons qu'un seul réveil réglé au plus tôt.
Nous allons maintenant apprendre à déterminer combien d'alarmes ont sonné à un certain moment T . Si l'alarme est réglée à l'heure ti , le nombre de ses appels au moment T sera égal
max Big( fracT−tiX,0 Big).
En ajoutant ces valeurs pour toutes les alarmes, nous obtenons le nombre total d'alarmes sonneries par heure T .
Après cela, le problème initial est résolu par une recherche binaire par T : avec augmentation T le nombre d'alarmes de sonnerie ne diminue pas (c'est-à-dire que la fonction est monotone); vous pouvez sélectionner 0 comme bordure gauche initiale et la réponse maximale possible dans le problème avec la droite.
Tournoi sportif
Condition de tâchePendant que Masha était en vacances, ses collègues ont organisé un tournoi d'échecs dans le système olympique. Pendant le reste, Masha n'a pas prêté beaucoup d'attention à cette aventure, donc elle peut à peine se rappeler qui a joué avec qui (il n'y a même pas un mot sur l'ordre des jeux). Soudain, Masha a eu l'idée qu'il serait bien d'apporter un souvenir des vacances au vainqueur du tournoi. Masha ne sait pas qui a remporté le match final, mais elle peut facilement déterminer qui y a joué, si seulement elle se souvenait correctement des paires de joueurs. Aidez-la à vérifier si c'est le cas et à identifier des candidats possibles pour les gagnants.
Ce problème peut être résolu en restaurant le graphique des jeux du tournoi. Pour commencer, il est clair pour chaque participant à quel stade du tournoi il a atteint: cela est déterminé par le nombre de matchs avec sa participation.
Après cela, vous pouvez distribuer les jeux lors de visites. Disons que, dans tous les matchs du premier tour, l'un des participants a décollé au premier tour, et l'autre a décollé au plus tôt au second. Lors du traitement d'un jeu de tournée avec un numéro x il est nécessaire de vérifier que tous les participants à ce jeu ont actuellement joué le même nombre de jeux correspondant au nombre x sinon le tournoi n'est pas valide.
Après avoir restauré le schéma du tournoi, il ne reste plus qu'à déduire la réponse.
C. Jeu intéressant
Condition de tâchePetya et Vasya jouent à un jeu intéressant. Tout d'abord, Vasya annonce le nombre de points dont vous avez besoin pour marquer la fin du jeu. Puis Petya prend les cartes sur lesquelles sont écrits des nombres entiers non négatifs et commence à les disposer sur la table une par une. S'il y a un multiple de cinq sur la carte, Vasya obtient un point. S'il y a un multiple de trois sur la carte, alors un point obtient Petya. S'il y a un nombre sur la carte qui n'est pas un multiple de trois ou cinq, ou vice versa, un multiple des deux, alors personne n'obtient de points.
Dès qu'un des participants gagne le nombre de points que Vasya a nommé au début du jeu, le jeu s'arrête et ce joueur devient le gagnant. Si aucun des participants n'a marqué le nombre de points requis, mais en même temps toutes les cartes sont terminées, alors le joueur avec le plus de points est considéré comme le gagnant. Si toutes les cartes sont terminées et que les points sont également répartis, un tirage est déclaré.
Petya et Vasya sont parfois pressés, ils ne veulent donc pas jouer complètement le jeu, mais découvrent immédiatement qui gagnerait avec les données initiales connues. Ils vous ont demandé d'écrire un programme qui vous aidera à répondre à cette question.
La chose la plus importante dans cette tâche est de comprendre correctement à partir de la condition lequel des joueurs et combien de points sont attribués après chaque nouveau coup, et aussi dans quelles conditions le joueur les gagne.
Le problème est résolu de manière simple. Étant donné que les restrictions sont plus que douces, il suffit de parcourir les données une fois, interrompant leur traitement, si l'un des joueurs à l'étape suivante a marqué le nombre de points requis. Si le nombre minimum de points requis n'a été marqué par aucun des joueurs, le vainqueur est déterminé à la fin du cycle.
Dans certaines versions de cette tâche, il était nécessaire de gérer davantage la situation dans laquelle les joueurs pouvaient recevoir des points en même temps pour la même carte.
Cette tâche était vraisemblablement la plus facile de toutes les tâches de qualification.
Analyseur d'exceptions
Condition de tâcheNous décrivons la syntaxe d'un langage de programmation EX :
func f() {...} - déclaration de fonction (entre crochets - le corps)maybethrow Exc est une commande qui peut maybethrow Exc une exception de type Exc ou ne pas lancer.try {...} suppress Exc - si une exception de type Exc se produit à l'intérieur de ce bloc, elle est supprimée.f() est un appel à f .
Dans la langue EX toutes les instructions, à l'exception des déclarations de fonctions, ne peuvent être que dans le corps d'une fonction. Les fonctions ne peuvent pas être déclarées à l'intérieur d'autres fonctions. Une fonction peut être appelée avant d'être définie, ainsi que dans son propre corps. Noms des fonctions et exceptions dans la langue EX doit correspondre à l'expression régulière [a−zA−Z0−9 ]+ , être unique et ne pas correspondre aux mots clés func , try , suppress , maybethrow .
Un programme en langue est entré EX et nombre x . Pour chaque fonction du programme, pas plus de x exceptions qui peuvent s'en échapper. Devrait sortir x exceptions lexicographiquement les plus petites.
Cette tâche s'est avérée être la plus difficile de toutes les tâches de qualification.
Pour le résoudre, il a été possible d'analyser syntaxiquement le programme en construisant un graphe d'appels de fonction: dans ce graphe, chaque fonction correspond à un sommet, et à l'appel de fonction, une arête. Après cela, il est nécessaire d'implémenter directement la logique de la distribution des exceptions à travers le graphique - pour cela, une traversée de graphique en largeur convient.
Nous choisirons une exception et toutes les fonctions qui peuvent y donner lieu. Ces fonctions sont appelées à partir d'autres fonctions; peut-être que les appels se trouvent dans le bloc try {...} suppress - dans ce cas, l'exception ne s'applique pas à la fonction dans laquelle l'appel se produit. Ainsi, il est possible de déterminer toutes les fonctions à partir desquelles cette exception peut être levée en utilisant la traversée de largeur de graphe.
Une fois le bypass effectué pour toutes les exceptions possibles, il ne reste plus qu'à former une réponse.
E. Décodage
Condition de tâcheUn nouveau service est apparu sur Internet. Malheureusement, il n'a aucune documentation. Empiriquement, la chaîne s été reçue du serveur. Cependant, certains caractères de cette ligne sont codés - pour obtenir une vraie réponse, vous devez décoder cette ligne plusieurs fois. Comme il n'y a pas de documentation pour le service, pour d'autres expériences, il est nécessaire de déterminer le nombre maximal de fois que cette ligne peut être décodée de manière non triviale. La procédure de décodage est la suivante: vous devez rechercher toutes les sous-chaînes de la forme ~XY , où X et Y sont des chiffres hexadécimaux grands ou petits et les remplacer simultanément par un caractère avec un code ASCII 
(chaque sous-chaîne a la sienne). Le décodage est appelé trivial s'il n'y a pas de sous-chaînes de ce type.
Sur une seule ligne, imprimez le nombre maximal de décodages non triviaux consécutifs de la chaîne d'origine.
Nous considérerons les caractères de la chaîne source de manière séquentielle, de gauche à droite. Si l'ajout d'un autre caractère entraîne une séquence qui peut être décodée, vous devez le faire. Le décodage doit être répété le plus longtemps possible, c'est-à-dire tandis qu'à la fin de la ligne courante il y a une séquence de la forme définie par les conditions de la tâche.
Pour chaque caractère de la chaîne décodée résultante, vous devez vous rappeler combien de fois pour l'obtenir, vous avez dû décoder la chaîne d'origine. Il est clair que le caractère ajouté à la chaîne est décodé zéro fois. Si les symboles décodés participent à la prochaine opération de décodage r1,r2,...,rk fois, alors le symbole qu'ils ont formé nécessite max(r1,r2,...,rk)+1 opérations de décodage.
Laisser la chaîne décodée finale contenir des caractères a1,...,ak , pour obtenir lequel il fallait effectuer respectivement le décodage, r1,...,rk fois. Alors la réponse est la quantité
max(r1,...,rk).
F. Trouver un engagement de rupture
Condition de tâcheYandex Search met en œuvre la politique dite du «tronc vert»: tout code entrant dans le référentiel, avec quelques réserves, est garanti de ne pas casser l'assemblage et les tests.
Les tests, cependant, sont extrêmement difficiles, et les exécuter tous à chaque validation est peu pratique. Ainsi, pour les cas particulièrement difficiles, la procédure suivante est mise en œuvre: les tests sont exécutés avec une certaine régularité et un ensemble de validations est vérifié immédiatement. Ainsi, pendant un certain temps, n commits non testés peuvent tomber dans le coffre, parmi lesquels au moins un contient une erreur.
Dans une telle situation, le système de test doit détecter le nombre m du premier commit qui a cassé les tests. Ce nombre a la propriété suivante: toutes les validations avec des nombres inférieurs à m réussissent les tests et les validations avec des nombres supérieurs ou égaux à m échouent. La tâche garantit qu'un commit avec les propriétés spécifiées existe nécessairement et est unique.
Afin d'économiser des ressources, le système de test ne peut vérifier qu'un seul commit à la fois. Vous devez écrire un programme qui déterminera le nombre m.
Cette tâche a un prototype dans notre production: certains tests des composants de recherche sont vraiment trop compliqués, ils sont trop coûteux à exécuter pour chaque commit, et pour eux une procédure de recherche de pannes similaire à celle décrite dans la tâche est implémentée. Bien sûr, les développeurs peuvent utiliser la vérification pré-audit et, en règle générale, le faire, de sorte que cette procédure n'est pas si souvent nécessaire.
Différentes versions de la tâche différaient par le nombre de validations qui devaient être vérifiées en même temps.
La solution ici est assez simple: vous devez implémenter une version légèrement plus complexe de la recherche binaire . Supposons que si vous souhaitez vérifier quatre validations à la fois, vous devez diviser également le segment en cours avec quatre chiffres. Lors de la mise en œuvre, il faut veiller à éviter les boucles lorsque la longueur du segment est inférieure au nombre de validations vérifiées simultanément. Il convient également de noter que, selon les conditions du problème, vous pouvez vérifier le même commit plusieurs fois - parfois vous devez le faire, par exemple, s'il y a deux commits au total, et vous devez vérifier trois commits à la fois.
Les tâches du tour de qualification discutées sont disponibles en tant que formation Codeforces . Nous avons également fait une formation sur les tâches des finales .