🚴🏽 🍟 👨‍👦 Salir de la rueda de Sansara, el extremismo y un poco de cosas verdes: un análisis de las tareas del folleto GridGain en la conferencia Joker 2018 🔷 🎊 🏇🏿

La conferencia Joker se celebró los días 19 y 20 de octubre en San Petersburgo, el mejor evento para aquellos que aman las mismas cosas que a nosotros: informes geniales, comunicación con expertos avanzados en Java y tareas. No elogiaremos el tercer tema de tareas de GridGain ( 1 , 2 ), mejor citamos los comentarios de los participantes:

"Sus tareas parecían estúpidas y no relacionadas con TI"
"Excelentes tareas, como siempre (aunque no he dominado una)"
"Adicción en tareas"
"Tareas principales, como siempre"

Publicamos, según lo prometido, soluciones detalladas. Lo sacaron bajo el spoiler para que aquellos que se perdieron la conferencia pudieran probar suerte.

Tarea 1

Hace tres meses, escribimos esta tarea, pero en octubre de 2018, el presidente presentó la iniciativa de despenalizar 282 artículos, de los que estamos increíblemente felices, pero estábamos inquietos por rehacer los textos. Así que deja que todo permanezca en esta tarea como estaba. *

El centro en una carta supervisa la ubicación de memes abusivos, así como sus gustos y publicaciones en las redes sociales. Como parte de la transformación digital, toda la oficina del departamento de monitoreo ha sido reemplazada por inteligencia artificial. La innovación ayudó a calcular rápidamente la probabilidad de que los usuarios cambien de Me gusta a reenvíos para llevar el caso a los tribunales con éxito. Anteriormente, se emitió una condena de una sola letra con una probabilidad del 90% en 192 días. La automatización del proceso llevó los indicadores a 12 días con una probabilidad del 99,9%.

Pregunta: ¿cuántas veces el enfoque innovador aumentó la conversión de memasics a convicciones en 282, si la frecuencia de las oraciones tiene una distribución exponencial?

Solución al problema 1

* Después de nombrar citas y un trabajo en el stand de nuestro autor, puede recibir un obsequio de inmediato. Por supuesto, este es Yuri Khoy (Klinsky), "Gas Sector" y la canción "Homeless".

Según la condición inicial, ya que la frecuencia de las oraciones tiene una distribución exponencial, luego antes de la introducción del robot y después de que tengamos las siguientes expresiones para evaluar la probabilidad de que una oración se pronuncie en el tiempo ≤ t:

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

donde

$\ lambda_1, \ lambda_2$ - estos son parámetros desconocidos que especifican la frecuencia de las oraciones, t es el parámetro de tiempo, de acuerdo con la condición que resulta que:

$F_1 (192) = 0.9 \\ F_2 (12) = 0.999$

A partir de estas ecuaciones, los parámetros se expresan muy fácilmente.

$\ lambda_1, \ lambda_2$

$\ lambda_1 = - \ ln (1 - 0.9) / 192 \ sim = 0.012 \\ \ lambda_2 = - \ ln (1 - 0.999) / 12 \ sim = 0.576$

Suponiendo que el número de oraciones y el número de memasics están linealmente relacionados, podemos concluir que la razón

$\ lambda_1, \ lambda_2$ solo da el valor deseado:

$\ lambda_2 / \ lambda_1 \ sim = 48$

Tarea 2

Desde el punto de vista del budista Vasily, el código es perfecto, no cuando no hay nada que agregar, sino cuando no se puede eliminar nada. Impulsado por esta idea, nuestro Vasily decidió mejorar EpsilonGC y reveló al mundo Dzen-GC, un producto de pensamiento perfecto que no solo puede borrar la memoria del montón, sino que ni siquiera permite asignarlo. Obviamente, la asignación en la JVM con este innovador GC solo es posible en la pila y solo para tipos primitivos.

Para probar la nueva funcionalidad, Vasily decidió escribir una función en Java que encuentre un modo para 6 valores (modo es el valor en el conjunto de observaciones que ocurre con mayor frecuencia), es decir, tiene la siguiente firma:

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

Para acercarse a la iluminación, Vasily no declaró variables y métodos locales adicionales en su código, y también programó solo con el dedo meñique de su pie izquierdo.

Tarea: ayudar a Vasily en la implementación de esta función (está permitido usar todos los dedos).

Solución al problema 2

Intentemos descubrir cómo se podría resolver este problema si no hubiera restricciones tan estrictas. Simplemente diga que los valores se transfieren en una matriz, y es aconsejable no usar la memoria adicional (pero es posible un poco).

Luego notaremos las opciones que usan Map <Integer, Integer>, y notaremos que el modo es más conveniente para buscar en una matriz ordenada: si el valor se repite, todos los duplicados están cerca. Ordenamos la matriz y en una pasada (y dos variables) encontramos el valor con el número máximo de repeticiones.

Ahora tenga en cuenta que:

1) Puede ordenar los valores de forma recursiva.

 // 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) Tenemos solo 6 valores ordenados.
3) Si el valor se repite 3 veces (la mitad de todos los valores), ¡esto ya es un mod!
3.1) Si no, pero hay 2 repeticiones, ¡entonces este es un mod!
3.2) Si no hay valores duplicados, cualquier valor es un modo.

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

Hablando estrictamente, un problema puede tener muchas soluciones, pero nos gustó como el más simple y armonioso.

Tarea 3

Dos drogadictos decidieron salir de Matrix y entender cuál de ellos era el Elegido. Para hacer esto, obtuvieron 1 paquete de píldoras azules y 4 paquetes de píldoras rojas (paquetes del mismo tamaño), y para mejorar el efecto, decidieron beberlas con verde.

De repente, resultó que debido a la falla de Matrix (como pensaban los drogadictos), sus caras, que inicialmente tenían los colores RGB # 2D241D y # F4E3E1, comenzaron a cambiar dependiendo de la cantidad de tabletas y té verde utilizado: cada tableta (o 1 ml de té verde) aumentó linealmente la cantidad de la correspondiente Los colores en la cara del adicto.

Al mismo tiempo, el valor de cada componente RGB no puede exceder #FF, es decir, el uso adicional de tabletas o verde brillante no tiene ningún efecto. Zelenka inicialmente tenía varios viales completos de 20 ml cada uno, en total 2 veces menos en ml que el número total de tabletas en pedazos. Después del evento de salida de Matrix, en el que comió el segundo adicto
A 54 drogadictos rojos más que a los primeros drogadictos azules, no les quedaba nada.

Pregunta: ¿cuántas píldoras y billetes verdes usó cada adicto, si como resultado sus caras eran # F0FF6B y #FFFEFF, respectivamente, y se sabe que el dólar es 3 veces más fuerte que las píldoras rojas, que a su vez son 2 veces
más débil que el azul?

Solución al problema 3

Para comenzar, seleccionaremos entre los valores finales para los colores solo aquellos que sean estrictamente inferiores a 0xFF, porque, por condición, para el valor 0xFF solo podemos dar el borde inferior del potenciador de color utilizado. Estos son los valores 0xF0, 0x6B y 0xFE. Obtenemos las siguientes ecuaciones:

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

o

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

Aquí k es el coeficiente de acción de las píldoras rojas,

$col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}$ , - el número de amplificadores utilizados (las tabletas se miden en piezas, verde - en mililitros) del color correspondiente por el consumidor correspondiente. Además, sabemos que el segundo comió 54 píldoras rojas más que el primero azul, todo es simple:

$r_2 = 54 + b_1$

Se obtiene otra ecuación a partir de la condición sobre la relación entre el número de tabletas y mililitros de verde:

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

También tenemos de la relación entre tabletas rojas y azules:

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

Además, sabemos que hubo varias veces 20 ml de billetes verdes:

$(g_1 + g_2) = 20 z$ donde z es un entero no negativo.

Suponiendo que k es entero y que las píldoras se comen enteras (puede tomar el dólar como quiera), la única respuesta que se ajusta a lo siguiente:

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

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

Se puede obtener de manera bastante simple, por ejemplo, mediante el método que se describe a continuación.
Tenemos una proporción

$b_1 * k = 39$ . Las únicas factorizaciones de 39 son {1, 39}, {3, 13}. Por lo tanto, k solo puede tomar valores del conjunto {1, 3, 13, 39}. Probemos el valor "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.$

Pero al mismo tiempo

$g_1 + g_2$ debe ser un múltiplo de 20, lo que no es cierto para el valor (79.5 + 3).

Exactamente de la misma manera, se eliminan los valores "13" y "39". El único valor que queda para k es uno. Sustituyéndolo, no llegamos a contradicciones y obtenemos una respuesta.

De hecho, dado que en ninguna parte del problema se dice que el coeficiente de incremento lineal k del componente RGB rojo es un número entero, las soluciones son una familia completa, * incluso * si suponemos que el verde solo se consume en múltiplos de 1 ml, y las tabletas se consumen en su totalidad (que también no especificado por separado):

$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 es un entero no negativo.

Para obtener esta familia, debe deshacerse de k en las primeras 3 ecuaciones reescribiéndolas, por ejemplo, como:

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

luego resuelva el sistema de ecuaciones lineales de diofantina (naturalmente, incluido el resto de las ecuaciones reducidas a la forma adecuada). Si no asumimos que el verde se consume solo por volúmenes que son múltiplos de un mililitro, obtenemos un sistema no lineal de ecuaciones diofantinas, tomando g1 y g2 (que obviamente debería ser racional) para todo el numerador y denominador desconocido. Si resolvemos el problema en su forma más general (todos los valores son continuos), entonces hay aún más soluciones.

Ganadores

Es cierto que todas las tareas fueron resueltas por Alexey Ryzhikov y Valentin Shipilov. Además, Alexey Galkin, Anton Blinov, Ilya Perevozchikov y varios otros participantes recibieron premios. Felicidades

Salir de la rueda de Sansara, el extremismo y un poco de cosas verdes: un análisis de las tareas del folleto GridGain en la conferencia Joker 2018

Tarea 1

Tarea 2

Tarea 3

Ganadores

More articles: