Соревнование от Яндекс.Такси: разбор бэкенд-трека чемпионата по программированию

^{_{Вручение призов участникам трека бэкенда}}

Мы завершаем серию разборов второго чемпионата по программированию. В последние недели мы опубликовали разборы трёх треков: по ML, фронтенду и мобильной разработке. Осталось разобрать трек по бэкенду. Он оказался самым популярным: 2682 человека приняли участие в квалификации, 320 из них дошли до финала. Задачи для бэкенд-разработчиков придумала команда Яндекс.Такси.

Марсианские промокоды

^{Автор: Максим Педченко}

Ограничение времени	1 с
Ограничение памяти	64 МБ
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

После запуска Яндекс.Такси на Марсе прошло полгода. К марсианскому Новому Году Яндекс.Такси решило подарить марсианам промокоды. Но оказалось, что марсиане не могут использовать земные промокоды, так как сервера на Марсе не работают по земным правилам. Поэтому Яндекс.Такси придумало специальные марсианские промокоды.

Марсианский промокод генерируется следующим образом:

1. Генерируется ключ шифрования.
2. Ключ шифрования разбивается на подстроки случайной длины.
3. Из всех подстрок выбираются подстроки длины L.
4. Выбранные подстроки перемешиваются и конкатенируются.
5. Результат конкатенации является промокодом.

Задача:
Необходимо проверить, является ли введенный промокод валидным. Если промокод валиден — нужно вывести «YES». Если невалиден — «NO».

Форматы ввода/вывода, примеры и примечания

Формат ввода

<длина промокода>
<промокод>

<длина ключа>

<ключ>

<длина подстроки L>

Формат вывода

Валидность промокода: YES или NO.

Пример 1

Ввод	Вывод
6 ABCDEA 6 EAABCD 2	YES

Пример 2

Ввод	Вывод
12 MARS1234MARS 24 ASDGRV12MARSS1234VRCMARS 4	YES

Пример 3

Ввод	Вывод
12 ABC123123ABC 9 ABC123123 3	NO

Примечания

Длина L > 1.
Алфавит промокода [A-Z, 0-9].
Длина промокода находится в диапазоне [6, 30].
Длина ключа находится в диапазоне [6, 30].
Длина подстроки L < длина ключа.
Длина промокода кратна L.

Решение

Нужно рассмотреть все возможные разбиения ключа шифрования на подстроки длины L и проверить, можно ли из возможных разбиений составить данный промокод.

Подсказка скрывается в примечаниях к условию:

Длина промокода находится в диапазоне [6, 30].
Длина ключа находится в диапазоне [6, 30].

Небольшие ограничения говорят о том, что эффективное решение не требуется, а значит, не нужно тратить время на поиск оптимизации — лучше решать задачу в лоб.

Такая ситуация типична для продуктовой бэкенд-разработки. Часто возникают ситуации, когда можно потратить недели на оптимальный алгоритм, но если взвесить ограничения, станет ясно — лучше использовать быстрое и не самое оптимальное решение.

Итак, будем рассматривать строку с промокодом как последовательность подстрок S длины L. Для каждой подстроки S найдем все равные ей подстроки S_k из ключа шифрования. Для каждой S_k запомним ее использование, перейдем к следующей подстроке S и повторим алгоритм.

Если для подстроки S не удается найти неиспользованную S_k, необходимо попробовать другой вариант разбиения, если другого варианта нет — значит, промокод не валиден.

Если хотя бы в одном случае для каждой S удалось найти S_k — значит, промокод валиден.

Оптимизация транспортной системы Марса

^{Авторы: Дмитрий Полищук и Антон Тодуа}

Ограничение времени	3 с
Ограничение памяти	64 МБ
Ввод	стандартный ввод
Вывод	стандартный вывод

Шёл 2058 год. Колонии первых поселенцев уже высадились на Марсе и стали его обживать, а Яндекс.Такси начала развертывание системы шатл-станций.

Для нормального функционирования шатл-станция нуждается в постоянном питании от энергетической сети. Чтобы запитать станцию нужно либо построить урановый ядерный генератор энергии внутри самой станции, либо проложить кабель до другой (уже запитанной) шатл-станции. Стоимость строительства генератора внутри разных шатл-станций может отличаться. Проведение кабеля между шатл-станциями также варьируется по стоимости и не всегда возможно. Кабельное соединение является двунаправленным.

Задача состоит в том, чтобы организовать эффективное (с минимальной стоимостью) питание всех шатл-станций.

На вход программа получает общее число шатл-станций, стоимости строительства генераторов для каждой шатл-станции и описания всех возможных кабелей между шатл-станциями (номера соединяемых станций и стоимость прокладки кабеля).

Форматы ввода/вывода, примеры и примечания

Формат ввода

Первая строка содержит одно целое неотрицательное число шатл-станций N ≤ 1000.

Вторая строка содержит N чисел, задающих стоимости строительства генератора внутри соответствующей станции.

Третья строка содержит одно целое неотрицательное число возможных кабелей K ≤ 100000 между шатл-станциями.

Последующие K строк (начиная с четвёртой) содержат описание одного кабеля — три целых неотрицательных числа: номер первой станции, номер второй станции и стоимость проведения.

Формат вывода

Одно целое число — минимальная стоимость питания всех шатл-станций для заданной конфигурации.

Пример 1

Ввод	Вывод
1 77 0	77

Пример 2

Ввод	Вывод
2 11 29 1 1 2 17	28

Примечания

Станции нумеруются с единицы.
Числа внутри строки разделяются одним пробелом.
Корректность входных данных проверять не требуется.

Решение

Сначала стоит перейти от красивого описания к неориентированному взвешенному графу, где на месте шатл-станций будут вершины, кабели станут рёбрами, а стоимости построения кабелей превратятся в веса соответствующих рёбер. Но останется вопрос — как учесть в графе стоимости построения урановых генераторов внутри самих станций (вершин)? В ответе на этот вопрос и кроется суть задачи.

Предположим, есть ещё одна вершина — источник энергии, и от этой вершины проведено ребро в каждую из вершин графа с весом, равным стоимости строительства уранового генератора в соответствующей станции (вершине). Такое предположение приводит нас к связному графу, который нужно превратить в дерево так, чтобы сумма весов рёбер в нём оказалась минимальной из возможных. Это ни что иное, как задача о поиске минимального остовного дерева в графе. Строить минимальное остовное дерево можно любым из известных алгоритмов — например, Прима или Краскала.

Пример кода с комментариями

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

Стоянка запрещена

^{Авторы: Илья Мещерин и Артём Серебрийский}

	Все языки	Python 3.7.3 и Python 2.7
Ограничение времени	1 с	10 c
Ограничение памяти	256 МБ
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

В одном городе запретили машинам останавливаться, кроме как для посадки пасажира. А пассажир не согласен ждать больше 3 минут. В этом городе пешеход заказывает такси в точку X и указывает интервал в 180 секунд. Водитель должен приехать ровно в этот интервал. Если приехать раньше, то ожидать пассажира будет нельзя. Если приехать слишком поздно, то разозленный пассажир отменит заказ.

Из-за подобных ограничений в этом городе осталось всего Z водителей, каждый из которых в момент старта задачи находится в какой-то вершине графа дорожного движения. Система управления должна назначить наилучшего водителя из тех, которые успеют приехать в указанный интервал. Наилучшим водителем считается тот, который приедет на заказ максимально близко к началу интервала. Если таких водителей несколько, то любой из них.

Нужно для каждого водителя определить, успевает ли он приехать в указанный интервал, и если да — то к какому самому раннему моменту времени в указанном интервале он может приехать.

Формальное описание

Дано:

1. Ориентированный граф G с N вершинами и K ребрами, вершины пронумерованы от 0 до N–1, 0 ≤ N ≤ 10⁴, 0 ≤ K ≤ 10⁴. Каждому ребру соответствует время поездки в нем — целое число W, 10 ≤ W ≤ 10⁴.
2. Позиция заказа на графе ID_target.
3. Z позиций водителей на графе IDsource₂, 1 ≤ Z ≤ 10⁴.
4. Время t₀, 0 ≤ t₀ ≤ 600 — целое число.

Надо для каждого водителя найти такое t_min, что:

1. существует такой маршрут от IDsource_z водителя к ID_target, что водитель приезжает в t_min,
2. t_min ∈ [t₀; t₀ + 180],
3. и это самый ранний возможный t_min: t_min ≤ t_i для любого t_i, удовлетворяющего пунктам 1 и 2,
4. или убедиться, что такого t_min не существует.

Форматы ввода/вывода, примеры и примечания

Формат ввода

Граф задается в виде троек вершина-начало вершина-конец время-проезда.

Входные данные, каждый пункт на своей строке:

1. K — число ребер.
2. K троек ID ID Weight — начальная вершина ребра, конечная вершина ребра, за сколько машина проезжает ребро.
3. ID_targett₀ — вершина заказа [пробел] начало диапазона, когда надо приехать.
4. Z — количество водителей.
5. (Z раз) ID_z вершина следующего водителя.

Формат вывода

Для каждого водителя в том же порядке, что они пришли на вход, распечатать на отдельной строке вычисленное t_min или –1, если такого t_min не существует.

Пример 1

Ввод	Вывод
2 0 1 10 2 3 10 3 0 1 0	-1

Пример 2

Ввод	Вывод
2 0 1 10 2 3 10 1 0 1 0	10

Пример 3

Ввод	Вывод
1 0 1 10 1 100 1 0	-1

Примечания

1. Из вершины А в вершину Б могут идти несколько ребер, в т. ч. с одинаковым весом.
2. Допускаются ребра из А в А.
3. Допускается существование одновременно ребер (А->Б) и (Б->А) (циклы длиной 2).

Решение

Один водитель

Сначала разберем простой случай с одним водителем. Мерой ребер является время [проезда по нему], ограничения финиша выражены в этих же единицах, поэтому мы можем переформулировать задачу: «Водитель едет из точки A в точки Б по графу. Найти такой минимальный путь, что его длина лежит в отрезке [T, U]».

Самый простой способ это сделать — запустить модифицированную дейкстру из А в Б:

1. Модификация 1. Предположим, мы достали вершину из minQ и она уже была помечена черной (то есть минимальное расстояние до нее уже найдено). Тогда мы не игнорируем ее, а обрабатываем стандартным образом — кладем все ее смежные вершины с новым расстоянием обратно в minQ.
2. Останавливаем ее, только когда расстояние до текущей вершины minQ строго больше U.
3. Предположим, в процессе обхода мы встречаем вершину Б. Тогда, если текущее расстояние ≥ T, запоминаем его как ответ R. В этот момент дейкстру также можно прервать.

Тем самым, если у нас есть R, это минимальный путь с длиной в требуемом интервале.

Множество водителей

Решение в лоб — запустить алгоритм для каждого водителя. Но такое решение не проходит по ограничению времени. Надо научится выдавать ответ для каждого водителя за O(1).

Для этого модифицируем алгоритм для одного водителя:

1. Вместо дейкстры от водителя к точке заказа запустим дейкстру из точки заказа по графу с инвертированными (!) ребрами.
2. Воспользуемся тем фактом, что количество вершин тоже было ограниченно десятью тысячами. Заведем массив ответов R — для каждой вершины это минимальное время в диапазоне [T, U], когда до нее можно добраться от A.
3. В процессе обхода графа модифицированной дейкстрой, когда мы встречаем вершину j и если текущее расстояние до нее находится в искомом интервале [T,U ], заносим R: R_j = min(R_j, dist).

Затем для каждого водителя в вершине J можно запросом в R_j узнать, есть ли удовлетворяющий условиям путь и какова его длина.

Оптимизация minQ

Длина пути всегда целочисленна и ограничена сверху значением 781 — для заказа который сделан в t₀ = 600 последняя допустимая секунда приезда водителя — 780. В таком случае для реализации дейкстры нужно применить следующую реализацию minQ.

У нас есть массив Fringe размером [781]. В каждом элементе Fringe_i находится unordered_set, хранящий id всех вершин, до которых существует путь длины i.

1. Добавим вершину с расстоянием D:

fringe[D].insert(vertex);

2. Согласно условиям, минимальный вес ребра > 0. Поэтому вместо того, чтобы брать элементы из minQ по одному, можно пройтись по всему срезу:

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

Калькулятор стоимости поездки

^{Автор: Николай Фильченко}

	Все языки	Python 3.7.3 и Python 2.7
Ограничение времени	3 с	65 c
Ограничение памяти	64 МБ	256 МБ
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Нужно рассчитать стоимости поездок по заданной формуле. Каждая поездка характеризуется K целочисленными параметрами. Формула задается в обратной польской записи.

Допустимые операции:

• + - — сложение и вычитание;
• * / — умножение и целочисленное деление;
• < = — сравнение;
• ? — условный оператор. Если первый аргумент истина — возвращает второй аргумент, иначе — третий.

В формуле также используются переменные [a-z] и целые числа от -10⁹ до 10⁹.

Можно считать, что результаты всех операций в формуле не превышают 10⁹ по абсолютному значению. Результат операций сравнения используется только в качестве аргумента условного оператора.

Форматы ввода/вывода и примеры

Формат ввода

На первой строке одно число 1 ≤ K ≤ 26 — количество переменных.

На второй строке записана формула расчета цены (не более 3⋅10⁴ элементов). Все элементы разделены пробелами.

На третьей строке 1 ≤ N ≤ 10⁴ — число тестов.

Следующие N строк содержат по K целых чисел (–10⁹ ≤ v ≤ 10⁹) — значения переменных в алфавитном порядке.

Формат вывода

N строк, содержащих по одному целому числу — результаты подстановки каждого набора значений. Гарантируется, что результат выражения конечен и определен

Пример 1

Ввод	Вывод
1 a 2 2 + * 2 2 3	8 12

Пример 2

Ввод	Вывод
2 a b < 5 14 ? 2 10 5 5 10	14 5

Решение

Это задача на аккуратную реализацию и внимание. В решении есть два основных момента:

1. Само исходное выражение надо превратить в массив чисел и операций, чтобы не разбирать строку на каждый набор переменных.
2. Нужно помнить, что целочисленное деление на ноль приводит к SIGFPE, поэтому в операции деления стоит явно проверять, что знаменатель — не ноль. Исходя из гарантии конечности и определенности результата всего выражения можно понять: результат таких делений не участвует в конечном результате и находится в неиспользуемых ветках условных операторов, поэтому можно принять его любым (например, нулем).

---

Хабрапосты по теме:

• Разбор бэкенд-трека первого чемпионата
• Разборы треков второго чемпионата: ML, фронтенд, мобильная разработка
• Один стендап в Яндекс.Такси, или Чему нужно научить бэкенд-разработчика