Introduccion
Ya en octubre de 2018, recordamos con gusto el calendario de Adviento con las tareas de 2017 (las condiciones están
aquí ) y comenzamos a pensar en lo que se puede hacer este año. De varias ideas valiosas, elegimos una opción en la que seleccionamos diversas tareas "pegadizas", unidas por una hermosa historia de Año Nuevo.
No quedaba nada: en realidad, recoger tareas, componer una historia, hacer un sitio web con una tabla de clasificación, hermoso y muy unido con Yandex.Constest, y comenzar a principios de diciembre :-)
Resultado
Como saben, el apetito viene con la comida, y nos lanzamos de cabeza al proceso de resolver el contenido de las tareas y su implementación técnica. Cada hallazgo exitoso inspiró nuevas mejoras. Como resultado, creamos un servidor separado para una de las tareas, hicimos que el otro sea uno de optimización (todavía no tenemos una respuesta exacta), grabamos la música nosotros mismos, restauramos las distribuciones, ¡no nos aburrimos!
El resultado es:
Datos e historias interesantes
Se registraron 780 participantes, 333 personas comenzaron a resolver, 203 personas aprobaron con éxito al menos dos tareas.
Inicialmente, estimamos el tiempo neto para resolver todos los problemas en siete días para un participante no preparado y dos días para uno muy experimentado (también conocido como recién graduado del centro CS). El primer asistente de Santa Claus que resolvió correctamente las once tareas se completó aproximadamente un día, ¡dos más lograron el segundo!
Carta de uno de los participantes: “¡Buenas tardes! Debido a su concurso, detuve la oficina (40 personas) específicamente la segunda tarea sobre el café de Santa Claus, dame una pista por favor. Todos estamos muy atormentados ".
Analizando tareas
Términos
aquí .
Tarea D "Mensaje musical" (Mikhail Plotkin)Es muy simple resolver el problema, teniendo una educación musical mínima.
Un intento de encontrar una pista en el patrón rítmico no condujo al éxito. La siguiente idea fue sentarse al piano y escuchar la melodía que escuchó. Resultó la, do, mi, si, la, re, salt, mi. En una clave de sol como esta:
Después de las primeras tres notas, siguió una breve pausa, como si dividiera la frase musical en dos palabras. Solo quedaba escribir notas en la notación tradicional de letras (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = salt) y se abrieron dos palabras: ACE BADGE.
Sin ningún conocimiento de alfabetización musical, resolver un problema es más difícil. Por ejemplo, uno podría usar algún programa para procesar el sonido y descubrir las notas en sí mismas o las frecuencias de los sonidos en hertzios, y luego averiguar qué frecuencias corresponden a qué notas.
La tarea requería escribir cartas juntas sin separadores, por lo que la respuesta es ACEBADGE.
Tarea F "Bolsa de copos de nieve" (Mikhail Plotkin)El área del triángulo inicial es 1. A continuación, en el enésimo paso, se añaden t_n triángulos, cada uno de los cuales tiene un área s_n. El área total de la figura resultante se expresa como la suma de una serie infinita:
S = 1 + Σ (t_n * s_n), la suma sobre n es de 0 a ∞ (1)
En el paso cero, t_0 = 3, s_0 = 1/9, ya que el triángulo tiene 3 lados, en cada uno de los cuales se construye un triángulo con un lado 3 veces más pequeño que el original y, por lo tanto, un área 9 veces más pequeña que el área del triángulo original.
En cada paso siguiente, cada lado se convierte en 4 lados tres veces más pequeños, es decir
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.
Por lo tanto, el área requerida:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n), la suma sobre n es de 0 a ∞ (2)
El segundo término es la suma de una progresión geométrica infinitamente decreciente. Para calcularlo, usa la fórmula de la escuela
Σ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5.
Sustituyendo en la fórmula (2), obtenemos la respuesta:
S = 1 + 1/3 * 9/5 = 8/5 = 1.6
Tarea G y L "La ruta está construida" (Artyom Romanov)¡Gracias a Artyom
mehrunesartem por la solución! Por cierto, el gráfico que se utilizó en el problema G se basa en el metro de Londres :)
Para resolver este problema, utilizaremos una versión modificada de la búsqueda de amplitud. Obtenemos un vértice imaginario (fuente), desde el cual dibujamos bordes de peso cero en cada vértice del gráfico. Cada estado está determinado de forma única por la ruta pasada desde la fuente. Además, almacenaremos el tiempo dedicado y la alegría recibida.
Comenzamos una cola de prioridad con un tamaño fijo, en el que colocaremos el estado. Como una evaluación de las condiciones en la cola, utilizaremos la proporción de felicidad recibida con respecto al tiempo dedicado. Esta evaluación no es correcta, pero mostró buenos resultados en esta tarea.
En cada paso, obtendremos el estado con la mejor estimación de la cola y colocaremos los estados formados a partir de él en la cola. Con este enfoque, llevará mucho tiempo obtener el resultado final.
Para acelerar la solución, buscaremos la respuesta paso a paso. En cada paso, para buscar el próximo vértice en la ruta, borraremos la cola y colocaremos el estado actual en ella. Luego haremos un número fijo de pasos, actualizando simultáneamente el estado que brinda la mayor cantidad de alegría. Como el próximo vértice de la ruta, tomamos el vértice que sigue al último vértice del estado actual en la ruta del estado resultante que da la mayor cantidad de alegría. Repetimos las acciones realizadas hasta que podamos mejorar el estado actual.
Posibles mejoras.
- Utiliza las mejores heurísticas.
- Con esta implementación del algoritmo, aparecerán estados adicionales, ya que en cada paso agregaremos todos los estados que podrían provenir del actual. Para evitar esto, utilizando el algoritmo de Dijkstra, para cada vértice del gráfico, primero puede construir un árbol de caminos más cortos a todos los demás vértices y hacer transiciones no en un solo paso, sino a lo largo del árbol construido hasta llegar a los vértices en los que nunca hemos estado.
Estos cambios no dieron mejoras significativas, probablemente debido al hecho de que solo hubo una prueba cerrada, y no un grupo de pruebas generadas diferentes.
Tarea I "Osos-digitalizadores" (Alexander Samofalov)Veamos el
código fuente del servicio .
Se puede obtener una lista de todas las identificaciones disponibles para el usuario en
/data .
Si hay id, los datos se pueden obtener mediante una solicitud a la dirección
/data/id .
Para acceder a los datos, el servicio requiere un token para la autenticación. Tenemos un
token disponible, pero ha caducado y el servicio ya no lo acepta.
Veamos en el código
cómo se generan estos tokens . El token se obtiene encriptando JSON de la forma
{ “userId” : “id”, expireDate: “date”} y luego
{ “userId” : “id”, expireDate: “date”} en base64. El servicio utiliza RSA para el cifrado, y la clave pública se puede obtener mediante solicitud en
/key .
Hagamos una solicitud: e = 30593, n = 66043. Desde n es lo suficientemente pequeño, entonces podemos calcular fácilmente la clave privada.
Para hacer esto, descomponemos n en factores primos: 211 * 313.
Calculamos
la función de
Euler de n: φ (n) = (211 - 1) (313 - 1) = 65520.
Obtenemos d = e-1 (mod φ (n)) = 257.
El módulo del elemento inverso se puede calcular utilizando el
algoritmo euclidiano avanzado .
Después de calcular la clave privada, desciframos el token disponible para nosotros.
Obtenemos el siguiente JSON:
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}Tenga en cuenta que es
suficiente que el servicio para el usuario con el ID de usuario dado exista y expireDate sea menor que la hora actual en el servidor.
Es decir, conociendo userId, podemos generar un nuevo token válido.
Para hacer esto, tome expireDate lo suficientemente grande como para pasar la prueba, por ejemplo
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} .
Ciframos nuestro nuevo token utilizando la clave pública.
Después de hacer una solicitud a
/data , descubrimos que el usuario creó mensajes con identificadores del 1 al 4.
Los resolveremos todos.
Entre ellos hay una frase maravillosa:
Año Nuevo toca a la puerta, ¡ábrela pronto! .
Consejos para resolver otros problemas (de Artyom Romanov)Tarea A "Caja fuerte con letras"Puede notar que cada veinte pasos obtendrá el mismo número.
Tarea B "El secreto del profesor"Ordena las palabras en orden descendente de popularidad. Puede notar que cada palabra posterior aparece en aproximadamente 2, 3, 4, etc. veces menos que la palabra más popular. Ahora puedes restaurar la respuesta.
Tarea C "Desastre informático"Piense en el lenguaje de programación de espacios en blanco.
Tarea J "Bengala"Posible colocación:
Problema K "Patrón escarchado"Para resolver este problema, puede elegir cualquier triángulo conveniente, por ejemplo, el correcto, y calcular la respuesta para él.
Agradecimientos
Katya Lebedeva condujo y coordinó todo el proceso, desde la idea hasta la implementación. Katya Artamonova, Alina Mozhina, Sasha Komissarov y yo la ayudamos a completar las tareas. Lyosha Tolstikov escribió tres complejas fichas, Sasha Komissarov y Seryozha Zherevchuk crearon un servidor, Svyato y Seryozha crearon desinteresadamente un hermoso sitio web con una estrecha integración con las tareas: cada participante podía ver su progreso y su clasificación.