👨🏽‍🤝‍👨🏼 🧑 🐆 Sortir de la roue de Sansara, de l'extrémisme et d'un peu de vert - une analyse des tâches du livret GridGain à la conférence Joker 2018 ⛅️ 👰🏼 🚶🏼

La conférence Joker s'est tenue les 19 et 20 octobre à Saint-Pétersbourg - le meilleur événement pour ceux qui aiment les mêmes choses que nous: rapports sympas, communication avec des experts Java avancés et tâches. Nous ne louerons pas le troisième numéro des tâches de GridGain ( 1 , 2 ), nous citerons mieux les retours des participants:

"Leurs tâches semblaient stupides et sans rapport avec l'informatique"
"D'excellentes tâches, comme toujours (même si je n'en ai pas maîtrisé une)"
"La dépendance dans les tâches"
"Les tâches les plus importantes, comme toujours"

Nous publions, comme promis, des solutions détaillées. Ils l'ont fait sortir sous le spoiler pour que ceux qui ont raté la conférence puissent s'essayer.

Tâche 1

Il y a trois mois, nous avons écrit cette tâche, mais en octobre 2018, le président a proposé l'initiative de décriminaliser 282 articles, ce dont nous sommes incroyablement heureux, mais nous étions impatients de refaire les textes. Alors, que tout reste dans cette tâche telle qu'elle était. *

Le centre sur une lettre surveille le placement des mèmes offensants, ainsi que leurs goûts et reposts sur les réseaux sociaux. Dans le cadre de la transformation numérique, l'ensemble du bureau du service de veille a été remplacé par l'intelligence artificielle. Cette innovation a permis de calculer rapidement la probabilité que les utilisateurs passent des likes aux reposts afin de porter l'affaire devant les tribunaux. Auparavant, une condamnation à une seule lettre avait été prononcée avec une probabilité de 90% en 192 jours. L'automatisation du processus a porté les indicateurs à 12 jours avec une probabilité de 99,9%.

Question: combien de fois l'approche innovante a-t-elle augmenté de 282 la conversion des mémoires en condamnations, si la fréquence des peines a une distribution exponentielle?

Solution au problème 1

* Ayant nommé des citations et un travail sur le stand de notre auteur, vous pourriez immédiatement recevoir un cadeau. Bien sûr, c'est Yuri Khoy (Klinsky), "Gas Sector" et la piste "Homeless"

Selon la condition initiale, depuis la fréquence des phrases a une distribution exponentielle, puis avant l'introduction du robot et après nous avons les expressions suivantes pour évaluer la probabilité qu'une phrase soit prononcée dans le temps ≤ t:

$F_1 (t) = 1 - e ^ {- \ lambda_1 * t} \\ F_2 (t) = 1 - e ^ {- \ lambda_2 * t}$

où

$\ lambda_1, \ lambda_2$ - ce sont des paramètres inconnus qui spécifient la fréquence des phrases, t est le paramètre temps, selon la condition il s'avère que:

$F_1 (192) = 0,9 \\ F_2 (12) = 0,999$

A partir de ces équations, les paramètres s'expriment très facilement

$\ lambda_1, \ lambda_2$

$\ lambda_1 = - \ ln (1 - 0,9) / 192 \ sim = 0,012 \\ \ lambda_2 = - \ ln (1 - 0,999) / 12 \ sim = 0,576$

En supposant que le nombre de phrases et le nombre de mémoires sont liés linéairement, nous pouvons conclure que le rapport

$\ lambda_1, \ lambda_2$ donne juste la valeur souhaitée:

$\ lambda_2 / \ lambda_1 \ sim = 48$

Tâche 2

Du point de vue du bouddhiste Vasily, le code est parfait non pas quand il n'y a rien à y ajouter, mais quand rien ne peut être supprimé. Poussé par cette idée, notre Vasily a décidé d'améliorer EpsilonGC et a révélé au monde Dzen-GC - un produit de pensée parfaite, qui peut non seulement effacer la mémoire du tas, mais ne permet même pas de l'allouer. Évidemment, l'allocation dans la JVM avec ce GC innovant n'est possible que sur la pile et uniquement pour les types primitifs.

Pour tester la nouvelle fonctionnalité, Vasily a décidé d'écrire une fonction en Java qui trouve un mode pour 6 valeurs (le mode est la valeur de l'ensemble d'observations qui se produit le plus souvent), c'est-à-dire qu'il a la signature suivante:

public static int mode(int n0, int n1, int n2, int n3, int n4, int n5)

Pour se rapprocher de l'illumination, Vasily n'a pas déclaré de variables et de méthodes locales supplémentaires dans son code, et a également programmé uniquement avec le petit doigt de son pied gauche.

Tâche: aider Vasily dans la mise en œuvre de cette fonction (il est permis d'utiliser tous les doigts).

Solution au problème 2

Essayons de comprendre comment ce problème pourrait être résolu s'il n'y avait pas de restrictions aussi strictes. Dites simplement que les valeurs sont transférées dans un tableau, et il est conseillé de ne pas utiliser la mémoire supplémentaire (mais un peu est possible).

Ensuite, nous noterons les options qui utilisent Map <Integer, Integer>, et remarquerons que le mode est le plus pratique à rechercher dans un tableau trié: si la valeur est répétée, tous les doublons sont à proximité. Nous trions le tableau et en un seul passage (et deux variables) nous trouvons la valeur avec le nombre maximum de répétitions.

Notez maintenant que:

1) Vous pouvez trier les valeurs récursivement.

 // Expectation: if there are more than one mode, we are free to return any of them. // 2,2,3,3,4,4 has 3 modes : 2,3,4. I expect that 3 is correct answer. public static int mode (int a, int b, int c, int d, int e, int f){ // If arguments are not sorted, let's sort them with bubble sort :) if (a > b) return mode(b,a,c,d,e,f); if (b > c) return mode(a,c,b,d,e,f); if (c > d) return mode(a,b,d,c,e,f); if (d > e) return mode(a,b,c,e,d,f); if (e > f) return mode(a,b,c,d,f,e);

2) Nous n'avons que 6 valeurs triées.
3) Si la valeur est répétée 3 fois (la moitié de toutes les valeurs) - c'est déjà un mod!
3.1) Sinon, mais il y a 2 répétitions - alors c'est un mod!
3.2) S'il n'y a pas de valeurs en double, alors n'importe quelle valeur est un mode.

 // Check for mode with 3+ repeats. 3 repeats is enough to say value is a mode (3 is half of 6). // Since args are sorted, a == b && b == c is the same as a == c; if (a == c) return a; if (b == d) return b; if (c == e) return c; if (d == f) return d; // Check for 2 repeats. if (a == b) return a; if (b == c) return b; if (c == d) return c; if (d == e) return d; if (e == f) return e; return f; }

À strictement parler, un problème peut avoir de nombreuses solutions, mais nous l'avons aimé comme le plus simple et le plus harmonieux.

Tâche 3

Deux toxicomanes ont décidé de sortir de la matrice et de comprendre lequel d'entre eux était l'élu. Pour ce faire, ils ont obtenu 1 pack de pilules bleues et 4 packs de pilules rouges (packs de même taille), et afin d'améliorer l'effet, ils ont décidé de les boire avec du vert.

Soudain, il s'est avéré qu'en raison du problème de Matrix (comme le pensaient les toxicomanes), leurs visages, qui avaient initialement les couleurs RVB # 2D241D et # F4E3E1, ont commencé à changer en fonction du nombre de comprimés et d'eau verte utilisés: chaque comprimé (ou 1 ml d'eau verte) a augmenté linéairement la quantité de correspondant couleurs sur le visage du toxicomane.

Dans le même temps, la valeur de chaque composant RVB ne peut pas dépasser #FF, c'est-à-dire qu'une utilisation ultérieure de tablettes ou de vert brillant n'a aucun effet. Zelenka avait initialement plusieurs flacons pleins de 20 ml chacun, 2 fois moins au total en ml que le nombre total de comprimés en morceaux. Après l'événement de sortie de la matrice, dans lequel le deuxième toxicomane a mangé
54 comprimés rouges de plus que les premiers bleus, les drogués n'avaient plus rien.

Question: combien de pilules et de billets verts chaque toxicomane a-t-il utilisé si, par conséquent, leurs visages étaient respectivement # F0FF6B et #FFFEFF, et il est connu que le billet vert est 3 fois plus fort que les comprimés rouges, qui, à leur tour, sont 2 fois
plus faible que le bleu?

Solution au problème 3

Pour commencer, nous ne sélectionnerons parmi les valeurs finales pour les couleurs que celles strictement inférieures à 0xFF, car, par condition, pour la valeur 0xFF, nous ne pouvons donner que la bordure inférieure de l'amplificateur de couleur utilisé. Ce sont les valeurs 0xF0, 0x6B et 0xFE. On obtient les équations suivantes:

$r_1 * k = (0xF0 - 0x2D) = 195 \\ b_1 * 2k = (0x6B - 0x1D) = 78 \\ g_2 * 3k = (0xFE - 0xE3) = 27 \\$

ou

$r_1 * k = 195 \\ b_1 * k = 39 \\ g_2 * k = 9 \\$

Ici k est le coefficient d'action des pilules rouges,

col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}

$col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}$ , - le nombre d'amplificateurs utilisés (les comprimés sont mesurés en morceaux, verts - en millilitres) de la couleur correspondante par le consommateur correspondant. De plus, nous savons que le second a mangé 54 comprimés de plus que le premier bleu, tout est simple:

$r_2 = 54 + b_1$

Une autre équation est obtenue à partir de la condition sur le rapport entre le nombre de comprimés et les millilitres de vert:

$inline$

Nous avons également du rapport entre les comprimés rouges et bleus:

$(r_1 + r_2) = 4 (b_1 + b_2)$

De plus, on sait qu'il y avait plusieurs fois 20 ml de billets verts:

$(g_1 + g_2) = 20 z$ où z est un entier non négatif.

À partir de l'hypothèse que k est entier et que les pilules sont consommées entières (vous pouvez boire du billet vert comme vous le souhaitez), la seule réponse qui correspond à ce qui suit:

$r_1 = 195 \\ g_1 = 171 \\ b_1 = 39 \\$

$r_2 = 93 \\ g_2 = 9 \\ b_2 = 33 \\$

Il peut être obtenu tout simplement, par exemple, par la méthode décrite ci-dessous.
Nous avons un ratio

$b_1 * k = 39$ . Les seules factorisations de 39 sont {1, 39}, {3, 13}. Ainsi, k ne peut prendre des valeurs que de l'ensemble {1, 3, 13, 39}. Essayons la valeur "3".

$r_1 = 195/3 = 65, \\ b_1 = 39/3 = 13, \\ g_2 = 9/3 = 3, \\ r_2 = 54 + b1 = 54 + 13 = 67, \\ b_2 = ((r1 + r2) - 4 * b1) / 4 = (65 + 67 - 4 * 13) / 4 = 20, \\ g_1 = ((r1 + b1 + r2 + b2) - 2 * g2) / 2 = (65 + 13 + 67 + 20 - 2 * 3) / 2 = 79 / 2.$

Mais en même temps

$g_1 + g_2$ doit être un multiple de 20, ce qui n'est pas vrai pour la valeur (79,5 + 3).

Exactement de la même manière, les valeurs "13" et "39" sont supprimées. La seule valeur qui reste pour k est une. En le substituant, nous ne venons pas aux contradictions et n'obtenons pas de réponse.

En fait, puisque nulle part dans le problème il n'est dit que le coefficient d'incrémentation linéaire k de la composante RVB rouge est un entier, les solutions s'avèrent être une famille entière, * même * si nous supposons que le vert uniquement est consommé en multiples de 1 ml et que les comprimés sont consommés dans leur intégralité (ce qui non spécifié séparément):

$r_1 = 1040n + 195 \\ g_1 = 732n + 171 \\ b_1 = 208n + 39 \\$

$r_2 = 208n + 93 \\ g_2 = 48n + 9 \\ b_2 = 104n + 33 \\$
n est un entier non négatif.

Pour obtenir cette famille, vous devez vous débarrasser de k dans les 3 premières équations en les réécrivant, par exemple, comme:

$3 $ r_1 - 15 b_1 = 0, \\ 3 r_1 - 65 g_2 = 0, \\ 15b_1 - 65g_2 = 0, \\ $$

résoudre ensuite le système d'équations diophantiennes linéaires (naturellement, y compris le reste des équations réduites à la forme appropriée). Si nous ne supposons pas que le vert est consommé uniquement par des volumes qui sont des multiples d'un millilitre, nous obtenons un système non linéaire d'équations diophantiennes, en prenant g1 et g2 (qui devraient évidemment être rationnels) pour tout le numérateur et le dénominateur inconnus. Si nous résolvons le problème dans sa forme la plus générale (toutes les valeurs sont continues), alors il y a encore plus de solutions.

Les gagnants

Certes, toutes les tâches ont été résolues par Alexey Ryzhikov et Valentin Shipilov. En outre, des prix ont été reçus par Alexey Galkin, Anton Blinov, Ilya Perevozchikov et plusieurs autres participants. Félicitations!

Sortir de la roue de Sansara, de l'extrémisme et d'un peu de vert - une analyse des tâches du livret GridGain à la conférence Joker 2018

Tâche 1

Tâche 2

Tâche 3

Les gagnants

More articles: