Geekly articles weekly

Competencia de Yandex.Taxi: análisis de la pista de back-end del campeonato de programación


Presentación de premios a los participantes de la pista de back-end.

Estamos completando una serie de análisis del segundo campeonato de programación. En las últimas semanas, hemos publicado un análisis de tres pistas: ML, frontend y desarrollo móvil. Queda por analizar la pista en el backend. Resultó ser el más popular: 2682 personas participaron en la calificación, 320 de ellos llegaron a la final. Las tareas para desarrolladores de backend fueron inventadas por el equipo Yandex.Taxi.

Códigos promocionales marcianos

Autor: Maxim Pedchenko
Límite de tiempo1 s
Límite de memoria64 MB
Entrarentrada estándar o input.txt
Conclusiónsalida estándar o salida.txt
Han pasado seis meses desde el lanzamiento de Yandex.Taxi en Marte. Para el Año Nuevo marciano, Yandex.Taxi decidió dar códigos promocionales a los marcianos. Pero resultó que los marcianos no pueden usar los códigos de promoción de la Tierra, ya que los servidores en Marte no funcionan de acuerdo con las reglas de la Tierra. Por lo tanto, Yandex.Taxi ideó códigos promocionales especiales de Marte.

El código promocional marciano se genera de la siguiente manera:

  1. Se genera una clave de cifrado.
  2. La clave de cifrado se divide en subcadenas de longitud aleatoria.
  3. De todas las subcadenas, se seleccionan las subcadenas de longitud L.
  4. Las subcadenas seleccionadas se mezclan y concatenan.
  5. El resultado de la concatenación es un código promocional.

Desafío:
Es necesario verificar si el código promocional ingresado es válido. Si el código promocional es válido, debe imprimir "SÍ". Si no es válido, "NO".

Formatos de E / S, ejemplos y notas

Formato de entrada


<longitud del código promocional>
<código promocional>

<longitud clave>

<key>

<longitud de la subcadena L>

Formato de salida


Validez del código de promoción: SÍ o NO.

Ejemplo 1

EntrarConclusión
6
ABCDEA
6
EAABCD
2		YES

Ejemplo 2

EntrarConclusión
12
MARS1234MARS
24
ASDGRV12MARSS1234VRCMARS
4		YES

Ejemplo 3

EntrarConclusión
12
ABC123123ABC
9
ABC123123
3		NO

Notas


Longitud L> 1.
Alfabeto del código de promoción [AZ, 0-9].
La longitud del código promocional está en el rango [6, 30].
La longitud de la clave está en el rango [6, 30].
Longitud de la subcadena L <longitud de la clave.
La longitud del código promocional es un múltiplo de L.

Solución


Necesitamos considerar todas las particiones posibles de la clave de cifrado en subcadenas de longitud L y verificar si este código promocional puede estar compuesto de posibles particiones.

La pista está oculta en las notas de condición:
La longitud del código promocional está en el rango [6, 30].
La longitud de la clave está en el rango [6, 30].

Pequeñas restricciones indican que no se requiere una solución efectiva, lo que significa que no necesita perder tiempo buscando la optimización; es mejor resolver el problema de frente.

Esta situación es típica del desarrollo del backend del producto. A menudo hay situaciones en las que puede pasar semanas en el algoritmo óptimo, pero si considera las restricciones, queda claro que es mejor usar una solución rápida y no la más óptima.

Por lo tanto, consideraremos la línea con el código promocional como una secuencia de subcadenas S de longitud L. Para cada subcadena S, encontramos todas las subcadenas S k iguales de la clave de cifrado. Para cada S k, recuerde su uso, pase a la siguiente subcadena S y repita el algoritmo.

Si para la subcadena S no es posible encontrar S k sin usar, es necesario probar otra variante de división, si no hay otra variante, entonces el código promocional no es válido.

Si se encontró S k para al menos un caso para cada S, entonces el código de promoción es válido.

Optimización del sistema de transporte de Marte

Autores: Dmitry Polishchuk y Anton Todua
Límite de tiempo3 s
Límite de memoria64 MB
Entrarentrada estándar
Conclusiónsalida estándar
Era el año 2058. Las colonias de los primeros colonos ya habían aterrizado en Marte y comenzaron a habitarlo, y Yandex.Taxi comenzó a desplegar un sistema de estaciones de transbordador.

Para el funcionamiento normal, la estación de transporte necesita un suministro de energía constante de la red de energía. Para alimentar la estación, debe construir un generador de energía nuclear de uranio dentro de la misma estación, o tender un cable a otra estación de transporte (ya alimentada). El costo de construir un generador dentro de diferentes estaciones de transporte puede variar. El enrutamiento de cables entre estaciones de transporte también varía en costo y no siempre es posible. La conexión del cable es bidireccional.

La tarea es organizar la energía eficiente (con un costo mínimo) a todas las estaciones de transporte.

En la entrada, el programa recibe el número total de estaciones de lanzadera, el costo de construir generadores para cada estación de lanzadera y una descripción de todos los cables posibles entre las estaciones de lanzadera (número de estaciones conectadas y el costo de tender el cable).

Formatos de E / S, ejemplos y notas

Formato de entrada


La primera línea contiene un solo número no negativo de estaciones de lanzadera N ≤ 1000.

La segunda línea contiene N números que especifican el costo de construir el generador dentro de la estación correspondiente.

La tercera línea contiene un solo número no negativo de cables posibles K ≤ 100000 entre las estaciones de lanzadera.

Las siguientes líneas K (a partir de la cuarta) contienen una descripción de un cable: tres números enteros no negativos: el número de la primera estación , el número de la segunda estación y el costo de la ejecución .

Formato de salida


Un número entero es el costo mínimo de energía para todas las estaciones de lanzadera para una configuración dada.

Ejemplo 1

EntrarConclusión
1
77
0		77

Ejemplo 2

EntrarConclusión
2
11 29
1
1 2 17		28

Notas


Las estaciones están numeradas de uno.
Los números dentro de la línea están separados por un solo espacio.
No es necesario verificar la exactitud de los datos de entrada.

Solución


Primero, vale la pena pasar de una descripción hermosa a un gráfico ponderado no dirigido, donde habrá picos en el lugar de las estaciones de lanzadera, los cables se convertirán en bordes y el costo de construir cables se convertirá en los pesos de los bordes correspondientes. Pero la pregunta sigue siendo: ¿cómo tener en cuenta el costo de construir generadores de uranio dentro de las estaciones (picos)? La respuesta a esta pregunta es la esencia del problema.

Suponga que hay otro vértice: una fuente de energía, y se dibuja un borde desde este vértice a cada uno de los vértices del gráfico con un peso igual al costo de construir un generador de uranio en la estación correspondiente (vértice). Esta suposición nos lleva a un gráfico conectado que debe convertirse en un árbol para que la suma de los pesos de los bordes sea lo más pequeña posible. Esto no es más que el problema de encontrar el árbol de expansión mínimo en un gráfico. Puede construir un árbol de expansión mínimo utilizando cualquiera de los algoritmos conocidos, por ejemplo, Prima o Kraskal.

Código de muestra con comentarios
 #include <algorithm> #include <iostream> #include <tuple> #include <vector> using Price = std::size_t; using Vertex = std::size_t; using Transition = std::tuple<Price, Vertex, Vertex>; using Graph = std::vector<Transition>; //        ( ). class Equals { public: //    . explicit Equals(std::size_t size) { equals_.resize(size); //     . for (std::size_t i = 0; i < size; i++) { equals_[i] = i; } } //   v1  v2   true,    //      . bool Emplace(std::size_t v1, std::size_t v2) { while (v1 != v2) { if (v2 < v1) { std::swap(v1, v2); } auto& next_v2 = equals_[v2]; if (next_v2 == v2) { next_v2 = v1; return true; } v2 = next_v2; } return false; } private: std::vector<size_t> equals_; }; int main() { //   . std::size_t vertex_count = 0; std::cin >> vertex_count; if (vertex_count == 0) { std::cout << 0 << std::endl; return 0; } //    —   —   . vertex_count++; //  . Graph graph; graph.reserve(vertex_count); //       . for (Vertex i = 1; i < vertex_count; i++) { Price price = 0; std::cin >> price; graph.emplace_back(price, 0, i); } //    . std::size_t edge_count = 0; std::cin >> edge_count; for (std::size_t i = 0; i < edge_count; i++) { Price price = 0; Vertex from = 0, to = 0; std::cin >> from >> to >> price; graph.emplace_back(price, from, to); } //      . std::sort(graph.begin(), graph.end()); //      . // https://ru.wikipedia.org/wiki/_ Price result = 0; Equals equals{vertex_count}; for (const auto& [price, from, to] : graph) { if (equals.Emplace(from, to)) { result += price; } } //  . std::cout << result << std::endl; return 0; }

Sin estacionamiento

Autores: Ilya Mescherin y Artyom Serebriysky
Todos los idiomasPython 3.7.3 y Python 2.7
Límite de tiempo1 s10 s
Límite de memoria256 MB
Entrarentrada estándar o input.txt
Conclusiónsalida estándar o salida.txt
En una ciudad, los automóviles tenían prohibido detenerse, excepto para abordar a un pasajero. Y el pasajero no acepta esperar más de 3 minutos. En esta ciudad, un peatón ordena un taxi al punto X e indica un intervalo de 180 segundos. El conductor debe llegar exactamente a este intervalo. Si llega antes, no podrá esperar un pasajero. Si llega demasiado tarde, el pasajero enojado cancelará el pedido.

Debido a tales restricciones, solo los conductores Z permanecieron en esta ciudad, cada uno de los cuales al comienzo de la tarea se encuentra en la parte superior del gráfico de tráfico. El sistema de control debe designar al mejor conductor de aquellos que logran llegar al intervalo especificado. El mejor conductor es el que llega al pedido lo más cerca posible del comienzo del intervalo. Si hay varios controladores de este tipo, cualquiera de ellos.

Es necesario que cada conductor determine si tiene tiempo para llegar al intervalo indicado y, de ser así, a qué punto más temprano en el intervalo indicado puede llegar.

Descripción formal

Dado:

  1. Gráfico orientado G con N vértices y bordes K, los vértices están numerados de 0 a N - 1, 0 ≤ N ≤ 10 4 , 0 ≤ K ≤ 10 4 . Cada borde corresponde al tiempo de viaje en él: un entero W, 10 ≤ W ≤ 10 4 .
  2. Posición del pedido en la columna de destino de ID.
  3. Posiciones Z de los controladores en la columna IDsource 2 , 1 ≤ Z ≤ 10 4 .
  4. El tiempo t 0 , 0 ≤ t 0 ≤ 600 es un número entero.

Es necesario que cada conductor encuentre un tmin que:

  1. existe tal ruta desde la fuente de identificación del conductor z al objetivo de identificación que el conductor llega a t min ,
  2. t min ∈ [t 0 ; t 0 + 180],
  3. y este es el t min más temprano posible: t min ≤ t i para cualquier t i que satisfaga los puntos 1 y 2,
  4. o asegúrese de que tal t min no exista.

Formatos de E / S, ejemplos y notas

Formato de entrada


El gráfico se establece en forma de triples-top-top-end-end-time-triples triples.

Datos de entrada, cada elemento en su propia línea:

1. K es el número de aristas.
2. K triplica ID Peso de ID: el vértice inicial de la costilla, el vértice final de la costilla, cuánto conduce el automóvil la costilla.
3. ID de destino t 0 - parte superior del orden [espacio] el comienzo del rango cuando necesita llegar.
4. Z: la cantidad de conductores.
5. (Z veces) ID z es la parte superior del siguiente controlador.

Formato de salida


Para cada controlador, en el mismo orden en que ingresaron, imprima en una línea separada el t min calculado o –1 si dicho t min no existe.

Ejemplo 1

EntrarConclusión
2
0 1 10
2 3 10
3 0
1
0		-1

Ejemplo 2

EntrarConclusión
2
0 1 10
2 3 10
1 0
1
0		10

Ejemplo 3

EntrarConclusión
1
0 1 10
1 100
1
0		-1

Notas


1. Varios bordes pueden ir del vértice A al vértice B, incluidos los que tienen el mismo peso.
2. Se permiten costillas de A a A.
3. Se permite la existencia de aristas (A-> B) y (B-> A) al mismo tiempo (ciclos de longitud 2).

Solución


Conductor individual

Primero, analizaremos un caso simple con un controlador. La medida de las costillas es el tiempo [viaje en él], las restricciones del acabado se expresan en las mismas unidades, por lo que podemos reformular el problema: “El conductor va del punto A al punto B de acuerdo con el gráfico. Encuentre una ruta mínima tal que su longitud se encuentre en el segmento [T, U] ".

La forma más fácil de hacer esto es ejecutar un dijkstra modificado de A a B:

  1. Modificación 1. Supongamos que obtuvimos la parte superior de minQ y ya estaba marcado en negro (es decir, ya se ha encontrado la distancia mínima). Entonces no lo ignoramos, sino que lo procesamos de la manera estándar: coloque todos sus vértices adyacentes con la nueva distancia nuevamente en minQ.
  2. Solo lo detenemos cuando la distancia al vértice actual minQ es estrictamente mayor que U.
  3. Supongamos que encontramos el pico B durante el recorrido. Luego, si la distancia actual es ≥ T, lo recordamos como la respuesta R. En este punto, la dijkstra también se puede interrumpir.

Por lo tanto, si tenemos R, esta es la ruta mínima con una longitud en el intervalo requerido.

Muchos conductores

La solución para la frente es ejecutar un algoritmo para cada controlador. Pero tal solución no pasa por limitar el tiempo. Debemos aprender a dar una respuesta para cada controlador para O (1).

Para hacer esto, modificamos el algoritmo para un controlador:

  1. En lugar de dijkstra desde el controlador hasta el punto de orden, comenzamos la dijkstra desde el punto de orden de acuerdo con el gráfico con bordes invertidos (!).
  2. Aprovechamos el hecho de que el número de vértices también se limitó a diez mil. Vamos a obtener un conjunto de respuestas R: para cada vértice, este es el tiempo mínimo en el rango [T, U] cuando se puede alcanzar desde A.
  3. En el proceso de atravesar la gráfica de la dijkstroy modificada, cuando nos encontramos con el vértice j y si la distancia actual a él está en el intervalo deseado [T, U], ingresamos R: R j = min (R j , dist).

Luego, para cada controlador en el vértice J, se puede consultar R j para averiguar si hay una ruta que satisfaga las condiciones y cuál es su longitud.

Optimización MinQ

La longitud de la ruta siempre es entera y está limitada a 781 desde la parte superior: para un pedido que se realiza en t 0 = 600, el último segundo válido de la llegada del conductor es 780. En este caso, para implementar el dijkstra, debe usar la siguiente implementación de minQ.

Tenemos una matriz Fringe de tamaño [781]. En cada elemento de Fringe i hay un conjunto desordenado que almacena la identificación de todos los vértices a los que hay una ruta de longitud i.

1. Agregue un vértice con la distancia D:

 fringe[D].insert(vertex);

2. De acuerdo con las condiciones, el peso mínimo del borde es> 0. Por lo tanto, en lugar de tomar elementos de minQ uno a la vez, puede pasar por todo el corte:

 for(int i = 0; i < fringe.size(); ++i) { if(fringe[i].empty()) { continue; } for(auto& vertex : fringe[i]) { // Do some stuff ProcessVertex(vertex, i); } }

Calculadora de costos de viaje

Autor: Nikolay Filchenko
Todos los idiomasPython 3.7.3 y Python 2.7
Límite de tiempo3 s65 c
Límite de memoria64 MB256 MB
Entrarentrada estándar o input.txt
Conclusiónsalida estándar o salida.txt
Es necesario calcular el costo del viaje de acuerdo con la fórmula dada. Cada viaje se caracteriza por K parámetros enteros. La fórmula se da en la notación polaca inversa.

Operaciones permitidas:

  • + - - suma y resta;
  • * / - multiplicación y división de enteros;
  • <= - comparación;
  • ? - operador condicional. Si el primer argumento es verdadero, devuelve el segundo argumento; de lo contrario, el tercero.

La variable [az] y los enteros de -10 9 a 10 9 también se usan en la fórmula.

Podemos suponer que los resultados de todas las operaciones en la fórmula no exceden 10 9 en valor absoluto. El resultado de las operaciones de comparación se usa solo como argumento para el operador condicional.

Formatos de E / S y ejemplos

Formato de entrada


En la primera línea, un número 1 ≤ K ≤ 26 - el número de variables.

La segunda línea contiene la fórmula para calcular el precio (no más de 3⋅10 4 elementos). Todos los elementos están separados por espacios.

En la tercera línea, 1 ≤ N ≤ 10 4 es el número de pruebas.

Las siguientes N líneas contienen K enteros cada una (–10 9 ≤ v ≤ 10 9 ), los valores de las variables en orden alfabético.

Formato de salida


N líneas que contienen un número entero: los resultados de la sustitución de cada conjunto de valores. Se garantiza que el resultado de la expresión es finito y definido.

Ejemplo 1

EntrarConclusión
1
a 2 2 + *
2
2
3		8
12

Ejemplo 2

EntrarConclusión
2
ab < 5 14 ?
2
10 5
5 10		14
5

Solución


Esta es una tarea para una cuidadosa implementación y atención. Hay dos puntos principales en la solución:

  1. La expresión original en sí misma debe convertirse en una matriz de números y operaciones para no analizar la cadena en cada conjunto de variables.
  2. Debe recordarse que la división entera por cero conduce a SIGFPE, por lo que en la operación de división vale la pena verificar explícitamente que el denominador no es cero. Basado en la garantía de finitud y certeza del resultado de toda la expresión, podemos entender: el resultado de tales divisiones no está involucrado en el resultado final y está en ramas no utilizadas de operadores condicionales, por lo que puede aceptarlo con cualquiera (por ejemplo, cero).


Habraposty sobre el tema:

Source: https://habr.com/ru/post/483624/

More articles:


All Articles