✋🏿 🆕 ⏲️ Raus aus Sansaras Rad, Extremismus und ein bisschen Grünzeug - eine Analyse der Aufgaben aus dem GridGain-Booklet auf der Joker 2018-Konferenz 👨🏿‍✈️ 👎 🆖

Die Joker-Konferenz fand am 19. und 20. Oktober in St. Petersburg statt - die beste Veranstaltung für diejenigen, die das Gleiche lieben wie wir: coole Berichte, Kommunikation mit fortgeschrittenen Java-Experten und Aufgaben. Wir werden die dritte Ausgabe der Aufgaben von GridGain ( 1 , 2 ) nicht loben, wir zitieren besser das Feedback der Teilnehmer:

"Ihre Aufgaben schienen dumm und nicht mit der IT verbunden zu sein"
"Ausgezeichnete Aufgaben, wie immer (obwohl ich noch keine gemeistert habe)"
"Sucht in Aufgaben"
"Top Aufgaben, wie immer"

Wir veröffentlichen wie versprochen detaillierte Lösungen. Sie brachten es unter dem Spoiler heraus, damit diejenigen, die die Konferenz verpassten, sich versuchen konnten.

Aufgabe 1

Vor drei Monaten haben wir diese Aufgabe geschrieben, aber im Oktober 2018 kam der Präsident auf die Initiative, 282 Artikel zu entkriminalisieren, worüber wir uns unglaublich freuen, aber wir waren unruhig, die Texte zu wiederholen. Lassen Sie also alles in dieser Aufgabe so bleiben, wie es war. *

Das Center-on-a-Letter überwacht die Platzierung anstößiger Memes sowie deren Likes und Reposts in sozialen Netzwerken. Im Rahmen der digitalen Transformation wurde das gesamte Büro der Überwachungsabteilung durch künstliche Intelligenz ersetzt. Die Innovation hat dazu beigetragen, die Wahrscheinlichkeit zu berechnen, mit der Benutzer von Likes zu Reposts wechseln, um den Fall erfolgreich vor Gericht zu bringen. Zuvor wurde eine Verurteilung mit einem Buchstaben mit einer Wahrscheinlichkeit von 90% in 192 Tagen erlassen. Durch die Automatisierung des Prozesses wurden die Indikatoren mit einer Wahrscheinlichkeit von 99,9% auf 12 Tage gebracht.

Frage: Wie oft hat der innovative Ansatz die Umwandlung von Memasics in Überzeugungen um 282 erhöht, wenn die Häufigkeit von Sätzen exponentiell verteilt ist?

Lösung zu Problem 1

* Nachdem Sie Zitate und eine Arbeit am Stand unseres Autors benannt haben, können Sie sofort ein Geschenk erhalten. Das sind natürlich Yuri Khoy (Klinsky), "Gas Sector" und der Track "Homeless".

Nach dem Ausgangszustand, da Die Häufigkeit von Sätzen hat eine Exponentialverteilung, dann vor der Einführung des Roboters und nachdem wir die folgenden Ausdrücke zur Beurteilung der Wahrscheinlichkeit haben, dass ein Satz in der Zeit ≤ t ausgesprochen wurde:

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

wo

$\ lambda_1, \ lambda_2$ - Dies sind unbekannte Parameter, die die Häufigkeit von Sätzen angeben. T ist der Zeitparameter. Dabei stellt sich heraus, dass:

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

Aus diesen Gleichungen lassen sich die Parameter sehr leicht ausdrücken

$\ lambda_1, \ lambda_2$

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

Aus der Annahme, dass die Anzahl der Sätze und die Anzahl der Memasics linear zusammenhängen, können wir schließen, dass das Verhältnis

$\ lambda_1, \ lambda_2$ gibt nur den gewünschten Wert:

$\ lambda_2 / \ lambda_1 \ sim = 48$

Aufgabe 2

Aus der Sicht des buddhistischen Wassili ist der Code nicht perfekt, wenn nichts hinzugefügt werden muss, sondern wenn nichts entfernt werden kann. Angetrieben von dieser Idee entschied sich unser Vasily für die Verbesserung von EpsilonGC und enthüllte der Welt Dzen-GC - ein Produkt des perfekten Denkens, das den Heap-Speicher nicht nur löschen, sondern auch nicht einmal zuordnen kann. Offensichtlich ist die Zuordnung in der JVM mit diesem innovativen GC nur auf dem Stapel und nur für primitive Typen möglich.

Um die neue Funktionalität zu testen, hat Vasily beschlossen, eine Funktion in Java zu schreiben, die einen Modus für 6 Werte findet (Modus ist der Wert in der Gruppe der Beobachtungen, der am häufigsten auftritt), dh die folgende Signatur hat:

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

Um der Erleuchtung näher zu kommen, hat Vasily keine zusätzlichen lokalen Variablen und Methoden in seinem Code deklariert und auch nur mit dem kleinen Finger seines linken Fußes programmiert.

Aufgabe: Hilf Vasily bei der Implementierung dieser Funktion (es dürfen alle Finger benutzt werden).

Lösung zu Problem 2

Versuchen wir herauszufinden, wie dieses Problem gelöst werden könnte, wenn es keine so strengen Einschränkungen gäbe. Sagen Sie einfach, dass die Werte in einem Array übertragen werden und es ratsam ist, den zusätzlichen Speicher nicht zu verwenden (aber ein bisschen ist möglich).

Dann werden wir die Optionen notieren, die Map <Integer, Integer> verwenden, und feststellen, dass der Modus in einem sortierten Array am bequemsten zu suchen ist: Wenn der Wert wiederholt wird, sind alle Duplikate in der Nähe. Wir sortieren das Array und finden in einem Durchgang (und zwei Variablen) den Wert mit der maximalen Anzahl von Wiederholungen.

Beachten Sie nun Folgendes:

1) Sie können die Werte rekursiv sortieren.

 // 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) Wir haben nur 6 sortierte Werte.
3) Wenn der Wert dreimal wiederholt wird (die Hälfte aller Werte) - das ist schon ein Mod!
3.1) Wenn nicht, aber es gibt 2 Wiederholungen - dann ist dies ein Mod!
3.2) Wenn keine doppelten Werte vorhanden sind, ist jeder Wert ein Modus.

 // 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; }

Genau genommen kann ein Problem viele Lösungen haben, aber wir mochten es als das einfachste und harmonischste.

Aufgabe 3

Zwei Drogenabhängige beschlossen, aus der Matrix auszusteigen und zu verstehen, welcher von ihnen der Auserwählte war. Zu diesem Zweck erhielten sie 1 Packung blaue und 4 Packungen rote Pillen (Packungen gleicher Größe). Um den Effekt zu verstärken, beschlossen sie, sie mit Grün zu trinken.

Plötzlich stellte sich heraus, dass sich aufgrund des Matrix-Fehlers (wie Drogenabhängige dachten) ihre Gesichter, die ursprünglich die RGB-Farben # 2D241D und # F4E3E1 hatten, in Abhängigkeit von der Anzahl der verwendeten Tabletten und des verwendeten Grüntees zu ändern begannen: Jede Tablette (oder 1 ml grüner Tee) erhöhte linear die Menge des entsprechenden die Farben im Gesicht des Süchtigen.

Gleichzeitig darf der Wert jeder RGB-Komponente #FF nicht überschreiten, dh die weitere Verwendung von Tabletten oder Brillantgrün hat keine Auswirkung. Zelenka hatte anfangs mehrere volle Fläschchen mit jeweils 20 ml, insgesamt 2 mal weniger in ml als die Gesamtzahl der Tabletten in Stücken. Nach dem Exit-Ereignis aus der Matrix, in dem der zweite Süchtige gegessen hat
54 mehr rote Tabletten als die ersten blauen, drogenabhängigen hatten nichts mehr übrig.

Frage: Wie viele Pillen und Greenbacks hat jeder Süchtige verwendet, wenn seine Gesichter # F0FF6B bzw. #FFFEFF waren, und es ist bekannt, dass Greenback dreimal stärker ist als rote Pillen, die wiederum zweimal sind
schwächer als blau?

Lösung zu Problem 3

Zunächst wählen wir unter den Endwerten für die Farben nur diejenigen aus, die streng kleiner als 0xFF sind, da wir für den Wert 0xFF bedingt nur die untere Grenze des verwendeten Farbverstärkers angeben können. Dies sind die Werte 0xF0, 0x6B und 0xFE. Wir erhalten die folgenden Gleichungen:

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

oder

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

Hier ist k der Wirkungskoeffizient von roten Pillen,

$col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}$ , - die Anzahl der verwendeten Verstärker (Tabletten werden in Stücken gemessen, grün - in Millilitern) der entsprechenden Farbe durch den entsprechenden Verbraucher. Außerdem wissen wir, dass die zweite 54 mehr rote Pillen aß als die erste blaue, alles ist einfach:

$r_2 = 54 + b_1$

Eine andere Gleichung ergibt sich aus der Bedingung des Verhältnisses zwischen der Anzahl der Tabletten und den Millilitern Grün:

$2 * (g_1 + g_2) = (r_1 + b_1 + r_2 + b_2)$

Wir haben auch aus dem Verhältnis zwischen roten und blauen Tabletten:

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

Außerdem wissen wir, dass es mehrmals 20 ml Greenbacks gab:

$(g_1 + g_2) = 20 z$ Dabei ist z eine nicht negative ganze Zahl.

Unter der Annahme, dass k ganz ist und die Pillen ganz gegessen werden (Sie können Greenback trinken, wie Sie möchten), passt die einzige Antwort wie folgt:

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

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

Es kann zum Beispiel ganz einfach durch das nachstehend beschriebene Verfahren erhalten werden.
Wir haben ein Verhältnis

$b_1 * k = 39$ . Die einzigen Faktorisierungen von 39 sind {1, 39}, {3, 13}. Somit kann k nur Werte aus der Menge {1, 3, 13, 39} annehmen. Versuchen wir den Wert "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.$

Aber zur gleichen Zeit

$g_1 + g_2$ muss ein Vielfaches von 20 sein, was für den Wert (79,5 + 3) nicht gilt.

Genau so werden die Werte "13" und "39" eliminiert. Der einzige Wert, der für k übrig bleibt, ist eins. Wenn wir es ersetzen, kommen wir nicht zu Widersprüchen und bekommen eine Antwort.

Da nirgends im Problem gesagt wird, dass der lineare Inkrementkoeffizient k der roten RGB-Komponente eine ganze Zahl ist, sind die Lösungen eine ganze Familie, * selbst * wenn wir annehmen, dass Grün nur in Vielfachen von 1 ml konsumiert wird und die Tabletten in ihrer Gesamtheit konsumiert werden (was auch) nicht gesondert angegeben):

$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 ist eine nicht negative ganze Zahl.

Um diese Familie zu erhalten, müssen Sie k in den ersten drei Gleichungen entfernen, indem Sie sie wie folgt umschreiben:

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

Lösen Sie dann das System der linearen diophantinischen Gleichungen (natürlich einschließlich der übrigen auf die richtige Form reduzierten Gleichungen). Wenn wir nicht annehmen, dass Grün nur von Volumina verbraucht wird, die ein Vielfaches eines Milliliters sind, erhalten wir ein nichtlineares System diophantinischer Gleichungen, wobei g1 und g2 (die offensichtlich rational sein sollten) für den gesamten unbekannten Zähler und Nenner verwendet werden. Wenn wir das Problem in seiner allgemeinsten Form lösen (alle Werte sind stetig), gibt es noch mehr Lösungen.

Gewinner

Zwar wurden alle Aufgaben von Alexey Ryzhikov und Valentin Shipilov gelöst. Auch Alexey Galkin, Anton Blinov, Ilya Perevozchikov und mehrere andere Teilnehmer erhielten Preise. Glückwunsch!

Raus aus Sansaras Rad, Extremismus und ein bisschen Grünzeug - eine Analyse der Aufgaben aus dem GridGain-Booklet auf der Joker 2018-Konferenz

Aufgabe 1

Aufgabe 2

Aufgabe 3

Gewinner

More articles: