Présentation
Déjà en octobre 2018, nous nous sommes souvenus du calendrier de l'Avent avec les tâches de 2017 (les conditions sont
ici ) et
avons commencé à réfléchir à ce qui pouvait être fait cette année. Parmi plusieurs idées louables, nous avons choisi une option dans laquelle nous sélectionnons diverses tâches «accrocheuses», unies par une belle histoire du Nouvel An.
Il ne restait plus rien: en fait, reprendre des tâches, composer une histoire, créer un site Web avec un classement, beau et bien tricoté avec Yandex.Constest, et commencer début décembre :-)
Résultat
Comme vous le savez, l'appétit vient avec l'alimentation, et nous avons plongé tête baissée dans le processus d'élaboration du contenu des tâches et de leur mise en œuvre technique. Chaque découverte réussie a inspiré de nouvelles améliorations. En conséquence, nous avons créé un serveur séparé pour l'une des tâches, rendu l'autre optimisé (nous n'avons toujours pas de réponse exacte), enregistré la musique nous-mêmes, restauré les distributions - nous ne nous sommes pas ennuyés!
Le résultat est:
Faits et histoires intéressants
780 participants se sont inscrits, 333 personnes ont commencé à résoudre, 203 personnes ont réussi au moins deux tâches.
Initialement, nous avons estimé le temps net pour résoudre tous les problèmes à sept jours pour un participant non préparé et à deux jours pour un très expérimenté (alias fraîchement diplômé du centre CS). Le premier assistant du Père Noël qui a correctement résolu les onze tâches a été achevé environ une journée, deux autres ont réussi la seconde!
Lettre d'un des participants: «Bonjour! À cause de votre concours, j'ai arrêté le bureau (40 personnes) en particulier la deuxième tâche concernant le café du Père Noël, donnez-moi un indice s'il vous plaît. Nous sommes tous très tourmentés. »
Tâches d'analyse
Conditions
ici .
Tâche D «Message musical» (Mikhail Plotkin)Il est très simple de résoudre le problème, avec une éducation musicale minimale.
Une tentative de trouver un indice dans le schéma rythmique n'a pas abouti. L'idée suivante était de s'asseoir au piano et de reprendre la mélodie que vous avez entendue. Il s'est avéré la, faire, mi, si, la, re, sel, mi. Dans une clé de sol comme celle-ci:
Après les trois premières notes, une courte pause s'ensuivit, comme pour diviser la phrase musicale en deux mots. Il ne restait plus qu'à écrire des notes en notation traditionnelle (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = sel) et deux mots s'ouvraient: ACE BADGE.
Sans aucune connaissance de la culture musicale, résoudre un problème est plus difficile. Par exemple, on pourrait utiliser un programme pour traiter le son et trouver soit les notes elles-mêmes, soit les fréquences des sons en hertz, puis savoir quelles fréquences correspondent à quelles notes.
La tâche requise pour écrire des lettres ensemble sans séparateurs, donc la réponse est ACEBADGE.
Tâche F «Sac de flocons de neige» (Mikhail Plotkin)L'aire du triangle initial est 1. Ensuite, à la nième étape, t_n triangles sont ajoutés, chacun ayant une aire s_n. L'aire totale de la figure résultante est exprimée comme la somme d'une série infinie:
S = 1 + Σ (t_n * s_n), la somme sur n est de 0 à ∞ (1)
Au pas zéro, t_0 = 3, s_0 = 1/9, car le triangle a 3 côtés, sur chacun desquels un triangle est construit avec un côté 3 fois plus petit que l'original, et donc une aire 9 fois plus petite que l'aire du triangle d'origine.
À chaque étape suivante, chaque côté se transforme en 4 côtés trois fois plus petits, c'est-à-dire
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n.
Par conséquent, la zone requise:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n), la somme sur n est de 0 à ∞ (2)
Le deuxième terme est la somme d'une progression géométrique infiniment décroissante. Pour le calculer, utilisez la formule scolaire
Σ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5.
En remplaçant dans la formule (2), nous obtenons la réponse:
S = 1 + 1/3 * 9/5 = 8/5 = 1,6
Tâche G et L «La route est construite» (Artyom Romanov)Merci à Artyom
mehrunesartem pour la solution! Soit dit en passant, le graphique qui a été utilisé dans le problème G est basé sur le métro de Londres :)
Pour résoudre ce problème, nous utiliserons une version modifiée de la recherche en largeur d'abord. Nous obtenons un sommet imaginaire (source), à partir duquel nous dessinons des arêtes de poids nul à chaque sommet du graphique. Chaque état est uniquement déterminé par le chemin transmis depuis la source. De plus, nous conserverons le temps passé et la joie reçue.
Nous commençons une file d'attente prioritaire avec une taille fixe, dans laquelle nous mettrons l'état. Pour évaluer les conditions dans la file d'attente, nous utiliserons le rapport entre le bonheur reçu et le temps passé. Cette évaluation n'est pas correcte, mais a montré de bons résultats dans cette tâche.
À chaque étape, nous obtiendrons l'état avec la meilleure estimation de la file d'attente et placerons les états formés à partir de celui-ci dans la file d'attente. Avec cette approche, il faudra beaucoup de temps pour obtenir le résultat final.
Pour accélérer la solution, nous chercherons la réponse étape par étape. À chaque étape, pour rechercher le sommet suivant dans le chemin, nous effacerons la file d'attente et y placerons l'état actuel. Ensuite, nous ferons un nombre fixe d'étapes, en mettant à jour simultanément l'état qui donne le plus de joie. En tant que sommet suivant du chemin, nous prenons le sommet suivant le dernier sommet de l'état actuel dans le chemin de l'état résultant qui donne le plus de joie. Nous répétons les actions effectuées jusqu'à ce que nous puissions améliorer l'état actuel.
Améliorations possibles
- Utilisez les meilleures heuristiques.
- Avec cette implémentation de l'algorithme, des états supplémentaires apparaîtront, car à chaque étape nous ajouterons tous les états qui pourraient provenir de l'actuel. Pour éviter cela, vous pouvez d'abord utiliser l'algorithme Dijkstra pour chaque sommet du graphique pour créer un arbre des chemins les plus courts vers tous les autres sommets et effectuer des transitions non pas en une seule étape, mais sur l'arbre construit jusqu'à ce que nous atteignions les sommets auxquels nous n'avons jamais été.
Ces changements n'ont pas apporté d'améliorations significatives, probablement en raison du fait qu'il n'y avait qu'un seul test fermé, et non un groupe de tests générés différents.
Tâche I «Ours numériseurs» (Alexander Samofalov)Regardons le
code source du service .
Une liste de tous les identifiants disponibles pour l'utilisateur peut être obtenue sur
/data .
S'il existe un identifiant, les données peuvent être obtenues à l'aide d'une demande adressée à l'adresse
/data/id .
Pour accéder aux données, le service nécessite un jeton pour l'authentification. Nous avons un
jeton disponible, mais il a expiré et le service ne l'accepte plus.
Voyons dans le code
comment ces jetons sont générés . Le jeton est obtenu en encodant JSON de la forme
{ “userId” : “id”, expireDate: “date”} puis en l'encodant en base64. Le service utilise RSA pour le chiffrement et la clé publique peut être obtenue sur demande à
/key .
Faisons une demande: e = 30593, n = 66043. Depuis n est assez petit, alors nous pouvons facilement calculer la clé privée.
Pour ce faire, nous décomposons n en facteurs premiers: 211 * 313.
Nous calculons
la fonction d'Euler de n: φ (n) = (211 - 1) (313 - 1) = 65520.
On obtient d = e-1 (mod φ (n)) = 257.
L'élément modulo inverse peut être calculé en utilisant l'
algorithme euclidien avancé .
Après avoir calculé la clé privée, nous déchiffrons le jeton à notre disposition.
Nous obtenons le JSON suivant:
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}Notez qu'il
suffit que le service pour l'utilisateur avec l'ID utilisateur donné existe et expireDate soit inférieur à l'heure actuelle sur le serveur.
Autrement dit, en connaissant userId, nous pouvons générer un nouveau jeton valide.
Pour ce faire, prenez expireDate suffisamment grand pour passer le test - par exemple
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} .
Nous chiffrons notre nouveau jeton à l'aide de la clé publique.
Après avoir fait une demande à
/data , nous constatons que l'utilisateur a créé des messages avec des identifiants de 1 à 4.
Nous les trierons tous.
Parmi eux, une phrase merveilleuse: le
Nouvel An frappe à la porte, ouvre-le bientôt! .
Conseils pour résoudre d'autres problèmes (d'Artyom Romanov)Tâche A «Coffre-fort avec des lettres»Vous remarquerez peut-être que toutes les vingt étapes, vous obtiendrez le même numéro.
Tâche B «Le secret du professeur»Triez les mots par ordre décroissant de popularité. Vous remarquerez peut-être que chaque mot suivant apparaît dans environ 2, 3, 4, etc. fois moins que le mot le plus populaire. Vous pouvez maintenant restaurer la réponse.
Tâche C «Catastrophe informatique»Pensez au langage de programmation Whitespace.
Tâche J "Bengale"Placement possible:
Problème K «Frosty Pattern»Pour résoudre ce problème, vous pouvez choisir n'importe quel triangle pratique, par exemple le bon, et calculer la réponse pour cela.
Remerciements
L'ensemble du processus, de l'idée à la mise en œuvre, a été piloté et coordonné par Katya Lebedeva. Katya Artamonova, Alina Mozhina, Sasha Komissarov et moi l'avons aidée à terminer les tâches. Lyosha Tolstikov a écrit trois vérificateurs complexes, Sasha Komissarov et Seryozha Zherevchuk ont fait un serveur, Svyato et Seryozha ont fait un généreux site Web avec une intégration étroite avec des tâches: chaque participant pouvait voir ses progrès et son classement.