👨🏽‍🔧 🗼 👩🏻 Competição da Yandex.Taxi: análise da pista de back-end do campeonato de programação 🍯 ✡️ 🎵

^{_{Apresentação de prêmios aos participantes da faixa de back-end}}

Estamos concluindo uma série de análises do segundo campeonato de programação. Nas últimas semanas, publicamos uma análise de três faixas: ML, frontend e desenvolvimento móvel. Resta analisar a faixa no back-end. Acabou sendo o mais popular: 2682 pessoas participaram da qualificação, 320 delas chegaram à final. Tarefas para desenvolvedores de back-end foram inventadas pela equipe Yandex.Taxi.

Códigos promocionais marcianos

^{Autor: Maxim Pedchenko}

Prazo	1 s
Limite de memória	64 MB
Entrar	entrada padrão ou input.txt
Conclusão	saída padrão ou output.txt

Seis meses se passaram desde o lançamento do Yandex.Taxi em Marte. No ano novo marciano, a Yandex.Taxi decidiu dar códigos promocionais aos marcianos. Mas os marcianos não podem usar códigos promocionais da Terra, já que os servidores em Marte não funcionam de acordo com as regras da Terra. Portanto, o Yandex.Taxi criou códigos promocionais marcianos especiais.

O código promocional marciano é gerado da seguinte maneira:

Uma chave de criptografia é gerada.
A chave de criptografia é dividida em substrings de tamanho aleatório.
De todas as substrings, substrings de comprimento L são selecionadas.
As substrings selecionadas são misturadas e concatenadas.
O resultado da concatenação é um código promocional.

Desafio:
É necessário verificar se o código promocional inserido é válido. Se o código promocional for válido, você precisará imprimir "SIM". Se inválido, "NÃO".

Formatos de E / S, exemplos e notas

Formato de entrada

Formato de saída

Validade do código de promoção: SIM ou NÃO.

Exemplo 1

Entrar	Conclusão
`6 ABCDEA 6 EAABCD 2`	`YES`

Exemplo 2

Entrar	Conclusão
`12 MARS1234MARS 24 ASDGRV12MARSS1234VRCMARS 4`	`YES`

Exemplo 3

Entrar	Conclusão
`12 ABC123123ABC 9 ABC123123 3`	`NO`

Anotações

Comprimento L> 1.
Alfabeto do código de promoção [AZ, 0-9].
O comprimento do código promocional está no intervalo [6, 30].
O comprimento da chave está no intervalo [6, 30].
Comprimento da corda L <comprimento da tecla.
O comprimento do código promocional é um múltiplo de L.

Solução

Precisamos considerar todas as partições possíveis da chave de criptografia em substrings de comprimento L e verificar se esse código promocional pode ser composto de possíveis partições.

A dica está oculta nas notas de condição:

O comprimento do código promocional está no intervalo [6, 30].
O comprimento da chave está no intervalo [6, 30].

Pequenas restrições indicam que uma solução eficaz não é necessária, o que significa que você não precisa gastar tempo procurando otimização - é melhor resolver o problema de frente.

Essa situação é típica do desenvolvimento de back-end do produto. Muitas vezes, há situações em que você pode passar semanas no algoritmo ideal, mas se você pesar as restrições, fica claro que é melhor usar uma solução rápida e não a melhor.

Portanto, consideraremos a linha com o código promocional como uma sequência de substrings S de comprimento L. Para cada substring S, encontramos todos os substratos _Sk iguais a ele na chave de criptografia. Para cada S _k, lembre-se de seu uso, vá para a próxima substring S e repita o algoritmo.

Se para a substring S não for possível encontrar S _k não utilizado, é necessário tentar outra variante de divisão, se não houver outra variante, o código promocional não será válido.

Se S _k foi encontrado para pelo menos um caso para cada S, o código da promoção é válido.

Otimização do sistema de transporte Mars

^{Autores: Dmitry Polishchuk e Anton Todua}

Prazo	3 s
Limite de memória	64 MB
Entrar	entrada padrão
Conclusão	saída padrão

Era o ano de 2058. As colônias dos primeiros colonos já haviam desembarcado em Marte e começaram a habitá-lo, e Yandex.Taxi começou a implantar um sistema de estações de ônibus.

Para operação normal, a estação de transporte precisa de fornecimento constante de energia da rede de energia. Para alimentar a estação, você deve construir um gerador de energia nuclear de urânio dentro da própria estação ou colocar um cabo em outra estação de transporte (já alimentada). O custo de construção de um gerador dentro de diferentes estações de ônibus pode variar. O encaminhamento de cabos entre as estações de ônibus também varia em custo e nem sempre é possível. A conexão do cabo é bidirecional.

A tarefa é organizar energia eficiente (com custo mínimo) para todas as estações de transporte.

Na entrada, o programa recebe o número total de estações de transporte, o custo de construção de geradores para cada estação de transporte e uma descrição de todos os cabos possíveis entre as estações de transporte (número de estações conectadas e o custo de instalação do cabo).

Formatos de E / S, exemplos e notas

Formato de entrada

A primeira linha contém um único número não negativo de estações de transporte N ≤ 1000.

A segunda linha contém N números que especificam o custo de construção do gerador dentro da estação correspondente.

A terceira linha contém um único número não negativo de possíveis cabos K ≤ 100000 entre as estações de transporte.

As próximas linhas K (começando no quarto) contêm uma descrição de um cabo - três números inteiros não negativos: o número da primeira estação , o número da segunda estação e o custo de execução .

Formato de saída

Um número inteiro é o custo mínimo de energia para todas as estações de transporte para uma determinada configuração.

Exemplo 1

Entrar	Conclusão
`1 77 0`	`77`

Exemplo 2

Entrar	Conclusão
`2 11 29 1 1 2 17`	`28`

Anotações

As estações são numeradas de uma.
Os números dentro da linha são separados por um único espaço.
A correção dos dados de entrada não precisa ser verificada.

Solução

Primeiro, vale a pena passar de uma bela descrição para um gráfico ponderado não direcionado, onde haverá picos no lugar das estações de ônibus, os cabos se tornarão arestas e o custo de construção de cabos se transformará nos pesos das arestas correspondentes. Mas a questão permanece - como levar em conta o custo de construção de geradores de urânio dentro das próprias estações (picos)? A resposta a esta pergunta é a essência do problema.

Suponha que exista outro vértice - uma fonte de energia e uma aresta seja desenhada desse vértice para cada um dos vértices do gráfico com um peso igual ao custo de construir um gerador de urânio na estação correspondente (vértice). Essa suposição nos leva a um gráfico conectado que precisa ser transformado em uma árvore, de modo que a soma dos pesos das arestas seja o menor possível. Isso nada mais é do que o problema de encontrar a árvore de abrangência mínima em um gráfico. Você pode construir uma árvore de abrangência mínima usando qualquer um dos algoritmos conhecidos - por exemplo, Prima ou Kraskal.

Código de exemplo com comentários

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

Sem estacionamento

^{Autores: Ilya Mescherin e Artyom Serebriysky}

	Todas as línguas	Python 3.7.3 e Python 2.7
Prazo	1 s	10 s
Limite de memória	256 MB
Entrar	entrada padrão ou input.txt
Conclusão	saída padrão ou output.txt

Em uma cidade, os carros eram proibidos de parar, exceto para embarcar em um passageiro. E o passageiro não concorda em esperar mais de 3 minutos. Nesta cidade, um pedestre pede um táxi para o ponto X e indica um intervalo de 180 segundos. O motorista deve chegar exatamente nesse intervalo. Se você chegar mais cedo, não poderá esperar um passageiro. Se você chegar tarde demais, o passageiro irritado cancelará o pedido.

Devido a essas restrições, apenas os motoristas Z permaneceram nesta cidade, cada um dos quais no início da tarefa está no topo do gráfico de tráfego. O sistema de controle deve indicar o melhor motorista dentre aqueles que conseguem chegar ao intervalo especificado. O melhor piloto é aquele que chega ao fim o mais próximo possível do intervalo. Se houver vários desses drivers, qualquer um deles.

É necessário que cada motorista determine se tem tempo para chegar ao intervalo indicado e, em caso afirmativo, em que ponto inicial no intervalo indicado ele pode chegar.

Descrição formal

Dado:

Gráfico orientado G com N vértices e K arestas, os vértices são numerados de 0 a N - 1, 0 ≤ N ≤ 10 ⁴ , 0 ≤ K ≤ 10 ⁴ . Cada aresta corresponde ao tempo de viagem nele - um número inteiro W, 10 ≤ W ≤ 10 ⁴ .
Posição do pedido na coluna de _destino do ID.
Posições Z dos drivers na coluna IDsource ₂ , 1 ≤ Z ≤ 10 ⁴ .
O tempo t ₀ , 0 ≤ t ₀ ≤ 600 é um número inteiro.

É necessário que cada motorista encontre tais t _min que:

existe uma rota do IDs do driver _z para o _{destino do} ID que o motorista chega em t _min ,
t _min ∈ [t ₀ ; t ₀ + 180],
e este é o mais cedo possível t _min : t _min ≤ t _i para qualquer t _{i que} satisfaça os pontos 1 e 2,
ou certifique-se de que esse _minuto não exista.

Formatos de E / S, exemplos e notas

Formato de entrada

O gráfico é definido na forma de triplos triplos-top-top-end-end-time-travel.

Dados de entrada, cada item em sua própria linha:

1. K é o número de arestas.
2. K triplica o ID ID Weight - o vértice inicial da nervura, o vértice final da nervura, quanto o carro dirige a nervura.
3. Identifique o _destino t ₀ - no topo da ordem [espaço] no início do intervalo quando você precisar chegar.
4. Z - o número de drivers.
5. (Z vezes) O ID _{z é o} topo do próximo driver.

Formato de saída

Para cada driver, na mesma ordem em que eles entraram, imprima em uma linha separada o t _min calculado ou –1 se esse t _min não existir.

Exemplo 1

Entrar	Conclusão
`2 0 1 10 2 3 10 3 0 1 0`	`-1`

Exemplo 2

Entrar	Conclusão
`2 0 1 10 2 3 10 1 0 1 0`	`10`

Exemplo 3

Entrar	Conclusão
`1 0 1 10 1 100 1 0`	`-1`

Anotações

1. Várias arestas podem ir do vértice A ao vértice B, incluindo aquelas com o mesmo peso.
2. Costelas de A a A são permitidas.
3. A existência de arestas (A-> B) e (B-> A) ao mesmo tempo (ciclos de comprimento 2) é permitida.

Solução

Único motorista

Primeiro, analisaremos um caso simples com um driver. A medida das nervuras é o tempo [de deslocamento], as restrições de acabamento são expressas nas mesmas unidades, para que possamos reformular o problema: “O motorista vai do ponto A ao ponto B, conforme o gráfico. Encontre um caminho mínimo para que seu comprimento esteja no segmento [T, U] ".

A maneira mais fácil de fazer isso é executar um dijkstra modificado de A para B:

Modificação 1. Suponha que obtivemos o topo do minQ e ele já estava marcado em preto (ou seja, a distância mínima até ele já foi encontrada). Então não o ignoramos, mas processamos da maneira padrão - coloque todos os seus vértices adjacentes com a nova distância novamente em minQ.
Paramos apenas quando a distância ao vértice atual minQ é estritamente maior que U.
Suponha que encontremos o pico B. durante a travessia.Em seguida, se a distância atual for ≥ T, lembre-se disso como a resposta R. Nesse ponto, o dijkstra também pode ser interrompido.

Assim, se tivermos R, esse é o caminho mínimo com um comprimento no intervalo necessário.

Muitos motoristas

A solução para a testa é executar um algoritmo para cada driver. Mas essa solução não passa limitando o tempo. Devemos aprender a dar uma resposta para cada driver para O (1).

Para fazer isso, modificamos o algoritmo para um driver:

Em vez de dijkstra do driver para o ponto do pedido, iniciamos o dijkstra do ponto do pedido de acordo com o gráfico com arestas invertidas (!).
Aproveitamos o fato de que o número de vértices também foi limitado a dez mil. Vamos obter uma matriz de respostas R - para cada vértice, este é o tempo mínimo no intervalo [T, U] quando pode ser alcançado a partir de A.
No processo de percorrer o gráfico da dijkstroy modificada, quando encontramos o vértice j e se a distância atual a ele está no intervalo desejado [T, U], inserimos R: Rj = min (Rj, dist).

Então, para cada driver no vértice J, pode-se consultar Rj _para descobrir se existe um caminho que satisfaça as condições e qual é o seu comprimento.

Otimização MinQ

O comprimento do caminho é sempre inteiro e limitado a 781 a partir do topo - para um pedido feito em t ₀ = 600, o último segundo válido de chegada do driver é 780. Nesse caso, para implementar o dijkstra, você precisa usar a seguinte implementação do minQ.

Temos uma matriz de tamanho Fringe [781]. Em cada elemento de Fringe _i existe um conjunto não ordenado que armazena o id de todos os vértices para os quais existe um caminho de comprimento i.

1. Adicione um vértice com a distância D:

 fringe[D].insert(vertex);

2. De acordo com as condições, o peso mínimo da aresta é> 0. Portanto, em vez de pegar elementos de minQ, um de cada vez, você pode percorrer toda a fatia:

 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 custo de viagem

^{Autor: Nikolay Filchenko}

	Todas as línguas	Python 3.7.3 e Python 2.7
Prazo	3 s	65 c
Limite de memória	64 MB	256 MB
Entrar	entrada padrão ou input.txt
Conclusão	saída padrão ou output.txt

É necessário calcular o custo da viagem de acordo com a fórmula fornecida. Cada disparo é caracterizado por K parâmetros inteiros. A fórmula é dada na notação polonesa reversa.

Operações permitidas:

+ - - adição e subtração;
* / - multiplicação e divisão inteira;
<= - comparação;
? - operador condicional. Se o primeiro argumento for verdadeiro - retorna o segundo argumento, caso contrário - o terceiro.

A variável [az] e os números inteiros de -10 ⁹ a 10 ⁹ também ^são usados na fórmula.

Podemos supor que os resultados de todas as operações na fórmula não excedam 10 ⁹ em valor absoluto. O resultado das operações de comparação é usado apenas como argumento para o operador condicional.

Formatos e exemplos de E / S

Formato de entrada

Na primeira linha, um número 1 ≤ K ≤ 26 - o número de variáveis.

A segunda linha contém a fórmula para calcular o preço (não mais que ³ × 10 ⁴ elementos). Todos os elementos são separados por espaços.

Na terceira linha, 1 ≤ N ≤ 10 ⁴ é o número de testes.

As próximas N linhas contêm K números inteiros cada (–10 ⁹ ≤ v ≤ 10 ⁹ ) - os valores das variáveis em ordem alfabética.

Formato de saída

N linhas contendo um número inteiro - os resultados da substituição de cada conjunto de valores. É garantido que o resultado da expressão seja finito e definido

Exemplo 1

Entrar	Conclusão
`1 a 2 2 + * 2 2 3`	`8 12`

Exemplo 2

Entrar	Conclusão
`2 ab < 5 14 ? 2 10 5 5 10`	`14 5`

Solução

Esta é uma tarefa para implementação e atenção cuidadosas. Existem dois pontos principais na solução:

A expressão original em si deve ser transformada em uma matriz de números e operações para não analisar a cadeia de caracteres em cada conjunto de variáveis.
Deve-se lembrar que a divisão inteira por zero leva ao SIGFPE; portanto, na operação de divisão, vale a pena verificar explicitamente que o denominador não é zero. Com base na garantia de finitude e certeza do resultado de toda a expressão, podemos entender: o resultado de tais divisões não está envolvido no resultado final e está em ramos não utilizados de operadores condicionais, para que você possa aceitá-lo com qualquer (por exemplo, zero).

Habraposty sobre o tema:

Análise da pista de back-end do primeiro campeonato
Analisando as faixas do segundo campeonato: ML , front-end , desenvolvimento móvel
Um standup no Yandex.Taxi ou O que você precisa ensinar ao desenvolvedor de back-end

Competição da Yandex.Taxi: análise da pista de back-end do campeonato de programação

Apresentação de prêmios aos participantes da faixa de back-end

Códigos promocionais marcianos

Formato de entrada

Formato de saída

Exemplo 1

Exemplo 2

Exemplo 3

Anotações

Solução

Otimização do sistema de transporte Mars

Formato de entrada

Formato de saída

Exemplo 1

Exemplo 2

Anotações

Solução

Sem estacionamento

Formato de entrada

Formato de saída

Exemplo 1

Exemplo 2

Exemplo 3

Anotações

Solução

Calculadora de custo de viagem

Formato de entrada

Formato de saída

Exemplo 1

Exemplo 2

Solução

More articles:

^{_{Apresentação de prêmios aos participantes da faixa de back-end}}