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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

В одном городе запретили машинам останавливаться, кроме как для посадки пасажира. А пассажир не согласен ждать больше 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 не существует.

Решение

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

Сначала разберем простой случай с одним водителем. Мерой ребер является время [проезда по нему], ограничения финиша выражены в этих же единицах, поэтому мы можем переформулировать задачу: «Водитель едет из точки 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);
  }
}

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

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

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

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

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

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

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

Решение

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

1. Само исходное выражение надо превратить в массив чисел и операций, чтобы не разбирать строку на каждый набор переменных.

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

Автор: Эдуард

Источник