El primero de junio, se llevó a cabo la final de nuestro campeonato de programación . Los nombres de los ganadores ya se conocen. Pronto recibirán sus premios, y mientras tanto, comenzamos a publicar análisis de las tareas del campeonato. Primero, analizaremos las tareas de la etapa de calificación entre los desarrolladores de back-end.
La calificación dura una semana y el número de participantes en los miles, por lo que resulta que preparar tareas no es una tarea fácil. En total, tuvimos que hacer 24 tareas y dividirlas entre las cuatro opciones para que las opciones fueran comparables en complejidad.
Esta vez se nos ocurrieron seis tareas, para cada una de las cuales fue posible encontrar varias formulaciones alternativas: ¡una tarea inventada dio lugar a cuatro a la vez! Por lo tanto, las opciones resultaron ser lo más comparables posible.
Por lo tanto, no publicaré análisis de los 24 problemas. En cambio, analizaré las seis tareas de una de las opciones de calificación: otras se resuelven de manera similar.
A. alarmas
Condición de la tareaEl trabajo en la mayoría de las empresas de TI tiene muchas ventajas: no hay un código de vestimenta, a veces puedes trabajar de forma remota, colegas geniales e inteligentes y, por supuesto, ¡un horario gratuito! Sin embargo, un horario gratuito y la capacidad de trabajar de forma remota requieren mucha fuerza de voluntad.
Al programador Alexei le gusta trabajar de noche y no le gusta llegar tarde. Para despertarse con precisión por la mañana, Alexey comienza todas las noches. N alarmas en su teléfono. Cada despertador está configurado para que suene cada X minutos desde el momento en el que trajo. Por ejemplo, si se activó una alarma en un punto en el tiempo ti entonces él llamará a veces ti , ti+X , ti+2 cdotX Al mismo tiempo, si dos alarmas comienzan a sonar en un momento, solo se muestra una de ellas.
Se sabe que antes de despertarse, Alexey escucha todas las mañanas K despertadores, después de lo cual se despierta. Determine el momento en que Alex se despierta.
Todas las alarmas suenan en tiempos enteros, y todas las alarmas tienen el mismo período de repetición de llamada. Si se configuran dos alarmas en puntos de tiempo ti y tj , y estos puntos en el tiempo dan el mismo resto cuando se dividen por X , solo puede dejar una alarma, la que suena la primera.
Entonces, el primer paso es deshacerse de las alarmas innecesarias: las agruparemos por el valor del resto de la división por X y de cada grupo dejaremos solo una alarma configurada lo antes posible.
Ahora aprenderemos cómo determinar cuántas alarmas sonaron en un momento determinado T . Si la alarma se configura a tiempo ti , el número de sus llamadas por el momento T será igual
max Big( fracT−tiX,0 Big).
Agregando estos valores para todas las alarmas, obtenemos el número total de alarmas sonando por hora T .
Después de eso, el problema inicial se resuelve mediante la búsqueda binaria por T : con aumento T el número de alarmas sonoras no disminuye (es decir, la función es monótona); puede seleccionar 0 como el borde izquierdo inicial y la respuesta máxima posible en el problema con el derecho.
B. torneo deportivo
Condición de la tareaMientras Masha estaba de vacaciones, sus colegas organizaron un torneo de ajedrez en el sistema olímpico. Durante el resto, Masha no prestó mucha atención a esta aventura, por lo que apenas puede recordar quién jugó con quién (sobre el orden de los juegos, no hay duda). De repente, Masha tuvo la idea de que sería bueno llevar un recuerdo de las vacaciones al ganador del torneo. Masha no sabe quién ganó el juego final, pero puede descubrir fácilmente quién jugó en él, si solo recordara correctamente los pares de juego. Ayúdela a verificar si este es el caso e identifique posibles candidatos para los ganadores.
Este problema se puede resolver restaurando el gráfico de los juegos de torneo. Para empezar, está claro para cada participante qué etapa del torneo ha alcanzado: esto está determinado por el número de juegos con su participación.
Después de eso, puedes distribuir los juegos en giras. Digamos, en todos los juegos de la primera ronda, uno de los participantes despegó en la primera ronda, y el otro despegó no antes que en la segunda. Al procesar un juego de gira con un número x es necesario verificar que todos los participantes en este juego hayan jugado actualmente el mismo número de juegos correspondiente al número x de lo contrario, el torneo no es válido.
Después de restaurar el esquema del torneo, todo lo que queda es deducir la respuesta.
C. Interesante juego
Condición de la tareaPetya y Vasya están jugando un juego interesante. Primero, Vasya anuncia cuántos puntos necesitas anotar para que el juego termine. Luego Petia toma las cartas en las que se escriben enteros no negativos y comienza a colocarlas sobre la mesa una por una. Si hay un múltiplo de cinco en la tarjeta, entonces Vasya obtiene un punto. Si hay un múltiplo de tres en la tarjeta, entonces un punto obtiene Petya. Si hay un número en la tarjeta que no es un múltiplo de tres o cinco, o viceversa, un múltiplo de ambos, entonces nadie obtiene puntos.
Tan pronto como uno de los participantes gana el número de puntos que Vasya nombró al comienzo del juego, el juego se detiene y este jugador se convierte en el ganador. Si ninguno de los participantes obtuvo el número requerido de puntos, pero al mismo tiempo se terminaron todas las cartas, entonces el jugador con más puntos se considera el ganador. Si se acaban todas las cartas y los puntos se dividen en partes iguales, se declara un sorteo.
Petya y Vasya a veces tienen prisa, por lo que no quieren jugar el juego por completo, pero inmediatamente descubren quién ganaría con los datos iniciales conocidos. Le pidieron que escriba un programa que ayude a responder esta pregunta.
Lo más importante en esta tarea es comprender correctamente a partir de la condición cuál de los jugadores y cuántos puntos se otorgan después de cada nuevo movimiento, y también bajo qué condiciones los gana el jugador.
El problema se resuelve de manera directa. Dado que las restricciones son más que suaves, es suficiente revisar los datos una vez, interrumpiendo su procesamiento, si uno de los jugadores en el siguiente paso obtuvo el número requerido de puntos. Si ninguno de los jugadores ha puntuado el número mínimo de puntos requerido, el ganador se determina al final del ciclo.
En algunas versiones de esta tarea, era necesario manejar aún más la situación en la que los jugadores podían recibir puntos al mismo tiempo por la misma carta.
Se esperaba que esta tarea fuera la más fácil entre todas las tareas de calificación.
D. Analizador de excepciones
Condición de la tareaDescribimos la sintaxis de un lenguaje de programación. EX :
func f() {...} - declaración de función (entre paréntesis - el cuerpo)maybethrow Exc es un comando que puede lanzar una excepción de tipo Exc , o no puede lanzar.try {...} suppress Exc : si se produce una excepción de tipo Exc dentro de este bloque, se suprime.f() es una llamada a f .
En el idioma EX todas las instrucciones, excepto las declaraciones de funciones, solo pueden estar en el cuerpo de una función. Las funciones no se pueden declarar dentro de otras funciones. Se puede invocar una función antes de definirla, así como en su propio cuerpo. Nombres de funciones y excepciones en el idioma. EX debe coincidir con la expresión regular [a−zA−Z0−9 ]+ , sea único y no coincida con las palabras clave func , try , suppress , maybethrow .
Se ingresa un programa en lenguaje EX y numero x . Para cada función del programa, no más de x excepciones que pueden salir volando. Debe salida x excepciones lexicográficamente más pequeñas.
Esta tarea resultó ser la más difícil de todas las tareas de calificación.
Para resolverlo, fue posible analizar el programa sintácticamente construyendo un gráfico de llamadas a funciones: en este gráfico, cada función corresponde a un vértice, y a la llamada a la función, un borde. Después de eso, es necesario implementar directamente la lógica de la distribución de excepciones en todo el gráfico; para esto, es adecuado un recorrido transversal del ancho.
Elegiremos alguna excepción y todas las funciones que pueden dar lugar a ella. Estas funciones se llaman desde otras funciones; quizás las llamadas están dentro del bloque de try {...} suppress , en este caso la excepción no se aplica a la función en la que se produce la llamada. Por lo tanto, es posible determinar todas las funciones desde las cuales se puede lanzar esta excepción utilizando el recorrido del ancho del gráfico.
Una vez que se ha realizado el bypass para todas las posibles excepciones, solo queda formar una respuesta.
E. Decodificación
Condición de la tareaUn nuevo servicio ha aparecido en Internet. Lamentablemente, no tiene documentación. Empíricamente, la cadena s se recibió del servidor. Sin embargo, algunos caracteres de esta línea están codificados: para obtener una respuesta real, debe decodificar esta línea varias veces. Como no hay documentación para el servicio, para más experimentos es necesario determinar qué número máximo de veces se puede decodificar esta línea de manera no trivial. El procedimiento de decodificación es el siguiente: necesita encontrar todas las subcadenas de la forma ~XY , donde X e Y son dígitos hexadecimales grandes o pequeños y reemplazarlos simultáneamente con un carácter con un código ASCII 16X+Y (cada subcadena tiene la suya propia). La decodificación se llama trivial si no hay subcadenas de este tipo.
En una sola línea imprima el número máximo de decodificaciones consecutivas no triviales de la cadena original.
Consideraremos los caracteres de la cadena fuente secuencialmente, de izquierda a derecha. Si agregar otro carácter da como resultado una secuencia que puede decodificarse, debe hacerlo. La decodificación debe repetirse el mayor tiempo posible, es decir. mientras que al final de la línea actual hay una secuencia de la forma definida por las condiciones de la tarea.
Para cada carácter de la cadena decodificada resultante, debe recordar cuántas veces tuvo que decodificar la cadena original para obtenerla. Está claro que el carácter agregado a la cadena se decodifica cero veces. Si los símbolos decodificados participan en la siguiente operación de decodificación r1,r2,...,rk veces, entonces el símbolo que formaron requiere max(r1,r2,...,rk)+1 operaciones de decodificación
Deje que la cadena decodificada final contenga caracteres a1,...,ak , para obtener cuál era necesario llevar a cabo la decodificación, respectivamente, r1,...,rk tiempos Entonces la respuesta es la cantidad
max(r1,...,rk).
F. Encontrar un compromiso de ruptura
Condición de la tareaYandex Search implementa la llamada política de "tronco verde": cualquier código que ingrese al repositorio, con algunas advertencias, tiene la garantía de no romper el ensamblaje y las pruebas.
Sin embargo, las pruebas son extremadamente difíciles, y ejecutarlas todas en cada confirmación no es práctico. Entonces, para casos particularmente difíciles, se implementa el siguiente procedimiento: las pruebas se ejecutan con cierta regularidad y se verifica inmediatamente un conjunto de confirmaciones. Por lo tanto, durante algún tiempo n confirmaciones no probadas pueden caer en el tronco, entre las cuales al menos una contiene un error.
En tal situación, el sistema de prueba debería detectar el número m de la primera confirmación que rompió las pruebas. Este número tiene la siguiente propiedad: todas las confirmaciones con números menores que m pasan las pruebas con éxito, y las confirmaciones con números mayores o iguales a m fallan en las pruebas. La tarea garantiza que existe una confirmación con las propiedades especificadas y que es única.
Para ahorrar recursos, el sistema de prueba solo puede verificar una confirmación a la vez. Necesita escribir un programa que determine el número m.
Esta tarea tiene un prototipo en nuestra producción: algunas pruebas de componentes de búsqueda son realmente demasiado complicadas, son demasiado caras de ejecutar para cada confirmación, y para ellos se implementa un procedimiento para encontrar averías similares a las descritas en la tarea. Por supuesto, los desarrolladores pueden usar la verificación previa a la auditoría y, como regla, hacer esto, por lo que este procedimiento no es tan frecuente.
Las diferentes versiones de la tarea diferían en el número de confirmaciones que deben verificarse al mismo tiempo.
La solución aquí es bastante simple: necesita implementar una versión un poco más compleja de búsqueda binaria . Digamos, si desea verificar cuatro confirmaciones a la vez, debe dividir uniformemente el segmento actual con cuatro números. Durante la implementación, se debe tener cuidado para evitar bucles cuando la longitud del segmento es menor que el número de confirmaciones verificadas simultáneamente. También vale la pena señalar que, de acuerdo con las condiciones del problema, puede verificar el mismo compromiso varias veces; a veces tiene que hacer esto, por ejemplo, si hay dos compromisos totales, y necesita verificar tres compromisos a la vez.
Las tareas de la ronda de calificación discutidas están disponibles como capacitación de Codeforces . También hicimos un entrenamiento sobre las tareas de la final .