Вручение призов участникам трека бэкенда
Мы завершаем серию разборов второго чемпионата по программированию. В последние недели мы опубликовали разборы трёх треков: по ML, фронтенду и мобильной разработке. Осталось разобрать трек по бэкенду. Он оказался самым популярным: 2682 человека приняли участие в квалификации, 320 из них дошли до финала. Задачи для бэкенд-разработчиков придумала команда Яндекс.Такси.
Марсианские промокоды
Автор: Максим Педченко| Ограничение времени | 1 с |
| Ограничение памяти | 64 МБ |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Марсианский промокод генерируется следующим образом:
- Генерируется ключ шифрования.
- Ключ шифрования разбивается на подстроки случайной длины.
- Из всех подстрок выбираются подстроки длины L.
- Выбранные подстроки перемешиваются и конкатенируются.
- Результат конкатенации является промокодом.
Задача:
Необходимо проверить, является ли введенный промокод валидным. Если промокод валиден — нужно вывести «YES». Если невалиден — «NO».
Форматы ввода/вывода, примеры и примечания
<длина промокода>
<промокод>
<длина ключа>
<ключ>
<длина подстроки L>
Валидность промокода: YES или NO.
Длина L > 1.
Алфавит промокода [A-Z, 0-9].
Длина промокода находится в диапазоне [6, 30].
Длина ключа находится в диапазоне [6, 30].
Длина подстроки L < длина ключа.
Длина промокода кратна L.
Формат ввода
<длина промокода>
<промокод>
<длина ключа>
<ключ>
<длина подстроки L>
Формат вывода
Валидность промокода: YES или NO.
Пример 1
| Ввод | Вывод |
6 |
YES |
Пример 2
| Ввод | Вывод |
12 |
YES |
Пример 3
| Ввод | Вывод |
12 |
NO |
Примечания
Длина L > 1.
Алфавит промокода [A-Z, 0-9].
Длина промокода находится в диапазоне [6, 30].
Длина ключа находится в диапазоне [6, 30].
Длина подстроки L < длина ключа.
Длина промокода кратна L.
Решение
Нужно рассмотреть все возможные разбиения ключа шифрования на подстроки длины L и проверить, можно ли из возможных разбиений составить данный промокод.
Подсказка скрывается в примечаниях к условию:
Длина промокода находится в диапазоне [6, 30].
Длина ключа находится в диапазоне [6, 30].
Небольшие ограничения говорят о том, что эффективное решение не требуется, а значит, не нужно тратить время на поиск оптимизации — лучше решать задачу в лоб.
Такая ситуация типична для продуктовой бэкенд-разработки. Часто возникают ситуации, когда можно потратить недели на оптимальный алгоритм, но если взвесить ограничения, станет ясно — лучше использовать быстрое и не самое оптимальное решение.
Итак, будем рассматривать строку с промокодом как последовательность подстрок S длины L. Для каждой подстроки S найдем все равные ей подстроки Sk из ключа шифрования. Для каждой Sk запомним ее использование, перейдем к следующей подстроке S и повторим алгоритм.
Если для подстроки S не удается найти неиспользованную Sk, необходимо попробовать другой вариант разбиения, если другого варианта нет — значит, промокод не валиден.
Если хотя бы в одном случае для каждой S удалось найти Sk — значит, промокод валиден.
Оптимизация транспортной системы Марса
Авторы: Дмитрий Полищук и Антон Тодуа| Ограничение времени | 3 с |
| Ограничение памяти | 64 МБ |
| Ввод | стандартный ввод |
| Вывод | стандартный вывод |
Для нормального функционирования шатл-станция нуждается в постоянном питании от энергетической сети. Чтобы запитать станцию нужно либо построить урановый ядерный генератор энергии внутри самой станции, либо проложить кабель до другой (уже запитанной) шатл-станции. Стоимость строительства генератора внутри разных шатл-станций может отличаться. Проведение кабеля между шатл-станциями также варьируется по стоимости и не всегда возможно. Кабельное соединение является двунаправленным.
Задача состоит в том, чтобы организовать эффективное (с минимальной стоимостью) питание всех шатл-станций.
На вход программа получает общее число шатл-станций, стоимости строительства генераторов для каждой шатл-станции и описания всех возможных кабелей между шатл-станциями (номера соединяемых станций и стоимость прокладки кабеля).
Форматы ввода/вывода, примеры и примечания
Первая строка содержит одно целое неотрицательное число шатл-станций N ≤ 1000.
Вторая строка содержит N чисел, задающих стоимости строительства генератора внутри соответствующей станции.
Третья строка содержит одно целое неотрицательное число возможных кабелей K ≤ 100000 между шатл-станциями.
Последующие K строк (начиная с четвёртой) содержат описание одного кабеля — три целых неотрицательных числа: номер первой станции, номер второй станции и стоимость проведения.
Одно целое число — минимальная стоимость питания всех шатл-станций для заданной конфигурации.
Станции нумеруются с единицы.
Числа внутри строки разделяются одним пробелом.
Корректность входных данных проверять не требуется.
Формат ввода
Первая строка содержит одно целое неотрицательное число шатл-станций N ≤ 1000.
Вторая строка содержит N чисел, задающих стоимости строительства генератора внутри соответствующей станции.
Третья строка содержит одно целое неотрицательное число возможных кабелей K ≤ 100000 между шатл-станциями.
Последующие K строк (начиная с четвёртой) содержат описание одного кабеля — три целых неотрицательных числа: номер первой станции, номер второй станции и стоимость проведения.
Формат вывода
Одно целое число — минимальная стоимость питания всех шатл-станций для заданной конфигурации.
Пример 1
| Ввод | Вывод |
1 |
77 |
Пример 2
| Ввод | Вывод |
2 |
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 | |
Из-за подобных ограничений в этом городе осталось всего Z водителей, каждый из которых в момент старта задачи находится в какой-то вершине графа дорожного движения. Система управления должна назначить наилучшего водителя из тех, которые успеют приехать в указанный интервал. Наилучшим водителем считается тот, который приедет на заказ максимально близко к началу интервала. Если таких водителей несколько, то любой из них.
Нужно для каждого водителя определить, успевает ли он приехать в указанный интервал, и если да — то к какому самому раннему моменту времени в указанном интервале он может приехать.
Формальное описание
Дано:
- Ориентированный граф G с N вершинами и K ребрами, вершины пронумерованы от 0 до N–1, 0 ≤ N ≤ 104, 0 ≤ K ≤ 104. Каждому ребру соответствует время поездки в нем — целое число W, 10 ≤ W ≤ 104.
- Позиция заказа на графе IDtarget.
- Z позиций водителей на графе IDsource2, 1 ≤ Z ≤ 104.
- Время t0, 0 ≤ t0 ≤ 600 — целое число.
Надо для каждого водителя найти такое tmin, что:
- существует такой маршрут от IDsourcez водителя к IDtarget, что водитель приезжает в tmin,
- tmin ∈ [t0; t0 + 180],
- и это самый ранний возможный tmin: tmin ≤ ti для любого ti, удовлетворяющего пунктам 1 и 2,
- или убедиться, что такого tmin не существует.
Форматы ввода/вывода, примеры и примечания
Граф задается в виде троек вершина-начало вершина-конец время-проезда.
Входные данные, каждый пункт на своей строке:
1. K — число ребер.
2. K троек ID ID Weight — начальная вершина ребра, конечная вершина ребра, за сколько машина проезжает ребро.
3. IDtargett0 — вершина заказа [пробел] начало диапазона, когда надо приехать.
4. Z — количество водителей.
5. (Z раз) IDz вершина следующего водителя.
Для каждого водителя в том же порядке, что они пришли на вход, распечатать на отдельной строке вычисленное tmin или –1, если такого tmin не существует.
1. Из вершины А в вершину Б могут идти несколько ребер, в т. ч. с одинаковым весом.
2. Допускаются ребра из А в А.
3. Допускается существование одновременно ребер (А->Б) и (Б->А) (циклы длиной 2).
Формат ввода
Граф задается в виде троек вершина-начало вершина-конец время-проезда.
Входные данные, каждый пункт на своей строке:
1. K — число ребер.
2. K троек ID ID Weight — начальная вершина ребра, конечная вершина ребра, за сколько машина проезжает ребро.
3. IDtargett0 — вершина заказа [пробел] начало диапазона, когда надо приехать.
4. Z — количество водителей.
5. (Z раз) IDz вершина следующего водителя.
Формат вывода
Для каждого водителя в том же порядке, что они пришли на вход, распечатать на отдельной строке вычисленное tmin или –1, если такого tmin не существует.
Пример 1
| Ввод | Вывод |
2 |
-1 |
Пример 2
| Ввод | Вывод |
2 |
10 |
Пример 3
| Ввод | Вывод |
1 |
-1 |
Примечания
1. Из вершины А в вершину Б могут идти несколько ребер, в т. ч. с одинаковым весом.
2. Допускаются ребра из А в А.
3. Допускается существование одновременно ребер (А->Б) и (Б->А) (циклы длиной 2).
Решение
Один водитель
Сначала разберем простой случай с одним водителем. Мерой ребер является время [проезда по нему], ограничения финиша выражены в этих же единицах, поэтому мы можем переформулировать задачу: «Водитель едет из точки A в точки Б по графу. Найти такой минимальный путь, что его длина лежит в отрезке [T, U]».
Самый простой способ это сделать — запустить модифицированную дейкстру из А в Б:
- Модификация 1. Предположим, мы достали вершину из minQ и она уже была помечена черной (то есть минимальное расстояние до нее уже найдено). Тогда мы не игнорируем ее, а обрабатываем стандартным образом — кладем все ее смежные вершины с новым расстоянием обратно в minQ.
- Останавливаем ее, только когда расстояние до текущей вершины minQ строго больше U.
- Предположим, в процессе обхода мы встречаем вершину Б. Тогда, если текущее расстояние ≥ T, запоминаем его как ответ R. В этот момент дейкстру также можно прервать.
Тем самым, если у нас есть R, это минимальный путь с длиной в требуемом интервале.
Множество водителей
Решение в лоб — запустить алгоритм для каждого водителя. Но такое решение не проходит по ограничению времени. Надо научится выдавать ответ для каждого водителя за O(1).
Для этого модифицируем алгоритм для одного водителя:
- Вместо дейкстры от водителя к точке заказа запустим дейкстру из точки заказа по графу с инвертированными (!) ребрами.
- Воспользуемся тем фактом, что количество вершин тоже было ограниченно десятью тысячами. Заведем массив ответов R — для каждой вершины это минимальное время в диапазоне [T, U], когда до нее можно добраться от A.
- В процессе обхода графа модифицированной дейкстрой, когда мы встречаем вершину j и если текущее расстояние до нее находится в искомом интервале [T,U ], заносим R: Rj = min(Rj, dist).
Затем для каждого водителя в вершине J можно запросом в Rj узнать, есть ли удовлетворяющий условиям путь и какова его длина.
Оптимизация minQ
Длина пути всегда целочисленна и ограничена сверху значением 781 — для заказа который сделан в t0 = 600 последняя допустимая секунда приезда водителя — 780. В таком случае для реализации дейкстры нужно применить следующую реализацию minQ.
У нас есть массив Fringe размером [781]. В каждом элементе Fringei находится 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 | |
Допустимые операции:
- + - — сложение и вычитание;
- * / — умножение и целочисленное деление;
- < = — сравнение;
- ? — условный оператор. Если первый аргумент истина — возвращает второй аргумент, иначе — третий.
В формуле также используются переменные [a-z] и целые числа от -109 до 109.
Можно считать, что результаты всех операций в формуле не превышают 109 по абсолютному значению. Результат операций сравнения используется только в качестве аргумента условного оператора.
Форматы ввода/вывода и примеры
На первой строке одно число 1 ≤ K ≤ 26 — количество переменных.
На второй строке записана формула расчета цены (не более 3⋅104 элементов). Все элементы разделены пробелами.
На третьей строке 1 ≤ N ≤ 104 — число тестов.
Следующие N строк содержат по K целых чисел (–109 ≤ v ≤ 109) — значения переменных в алфавитном порядке.
N строк, содержащих по одному целому числу — результаты подстановки каждого набора значений. Гарантируется, что результат выражения конечен и определен
Формат ввода
На первой строке одно число 1 ≤ K ≤ 26 — количество переменных.
На второй строке записана формула расчета цены (не более 3⋅104 элементов). Все элементы разделены пробелами.
На третьей строке 1 ≤ N ≤ 104 — число тестов.
Следующие N строк содержат по K целых чисел (–109 ≤ v ≤ 109) — значения переменных в алфавитном порядке.
Формат вывода
N строк, содержащих по одному целому числу — результаты подстановки каждого набора значений. Гарантируется, что результат выражения конечен и определен
Пример 1
| Ввод | Вывод |
1 |
8 |
Пример 2
| Ввод | Вывод |
2 |
14 |
Решение
Это задача на аккуратную реализацию и внимание. В решении есть два основных момента:
- Само исходное выражение надо превратить в массив чисел и операций, чтобы не разбирать строку на каждый набор переменных.
- Нужно помнить, что целочисленное деление на ноль приводит к SIGFPE, поэтому в операции деления стоит явно проверять, что знаменатель — не ноль. Исходя из гарантии конечности и определенности результата всего выражения можно понять: результат таких делений не участвует в конечном результате и находится в неиспользуемых ветках условных операторов, поэтому можно принять его любым (например, нулем).
Хабрапосты по теме:
- Разбор бэкенд-трека первого чемпионата
- Разборы треков второго чемпионата: ML, фронтенд, мобильная разработка
- Один стендап в Яндекс.Такси, или Чему нужно научить бэкенд-разработчика
