В спортивном соревновании приняло участие $$$N$$$ команд. Результат каждого участника каждой команды оценивается в некоторую сумму призовых денег. Однако по правилам соревнования команде выдаётся только один приз. В качестве суммы приза команды организаторы хотели выбрать медиану призовых денег её участников, но призовой бюджет уже зафиксирован. Жюри хочет избежать обвинений в предвзятости, поэтому было решено распределить призы так, чтобы сумма абсолютных разностей по всем участникам между заработанными и полученными деньгами была минимальной.

Распределите призы между командами.

Лето уже в самом разгаре — а это значит, что нас всех ждут и дождливые, и жаркие дни. В дождь людям нужны зонты и дождевики, и производителям этих товаров крайне важно отслеживать рост интереса к ним. С другой стороны, производителям прохладительных напитков важны жаркие дни, когда на продвижение можно потратить бóльшие бюджеты.

Итак, владельцам рекламных объявлений определённых тематик требуется возможность управлять настройками показов в зависимости от погоды. В этой задаче вам потребуется реализовать простейшую версию этой функциональности — таргетинг на температуру в определённые диапазоны дней.

В вашем распоряжении есть исторические данные о температуре, а также прогноз на ближайшее будущее. А именно:

• температура сегодня (этот день имеет номер $$$0$$$);
• температура за прошедшие $$$N$$$ дней (вчерашний имеет номер $$$-1$$$, позавчерашний — $$$-2$$$ и так далее до дня $$$-N$$$, самого раннего из известных);
• прогноз температуры на ближайшие $$$N$$$ дней (завтрашний имеет номер $$$1$$$, послезавтрашний — $$$2$$$ и так далее до дня $$$N$$$).

Кроме того, есть данные о настройках показа $$$B$$$ рекламных объявлений. Каждому из них соответствуют четыре числа $$$t_{min}$$$, $$$t_{max}$$$, $$$d_{min}$$$, $$$d_{max}$$$, означающие, что объявление можно показывать только в том случае, если за период от дня $$$d_{min}$$$ до дня $$$d_{max}$$$ включительно температура принимала или примет значение от $$$t_{min}$$$ до $$$t_{max}$$$ включительно. При этом гарантируется, что $$$d_{min} \le 0 \le d_{max}$$$, то есть диапазон дней должен включать сегодняшний.

Обратите внимание, что температура не дискретна! Например, если вчера значение температуры было $$$-5$$$, а сегодня $$$-2$$$, то необходимо считать, что в период, включающий сегодняшний и вчерашний дни, температура принимала не только значения $$$-5$$$ и $$$-2$$$, но и $$$-4$$$ и $$$-3$$$ (и даже $$$-3{,}14$$$, но в этой задаче все входные данные целочисленны).

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

Уже не первый год в Байтландии идёт тяжелая борьба за быструю отрисовку страниц в интернете...

Одним из шагов к победе стало нововведение Баннерной крутилки: отдавать баннеры для нескольких блоков в одном ответе, тем самым сохранив дополнительные вызовы, а с ними и время. Однако оказалось, что совсем непросто разумно разбить полученные баннеры по блокам.

Имеется $$$N$$$ баннеров, которые мы хотим разбить на $$$K$$$ блоков. В ответе есть массив $$$P$$$, где $$$P_i$$$ — прогнозируемая польза от показа $$$i$$$-го баннера, а также массив $$$L$$$, где $$$L_{j}$$$ — возможная потеря внимания пользователя на $$$j$$$-й по счёту блок.

Аналитик Виталик тестирует гипотезы, которые должны в первую очередь повысить счастье пользователя. Сейчас он прорабатывает следующую метрику: для блока вводим функцию $$$f(Block_{s}) = P_{min} \cdot len(Block_{s}) - L_{s} P_{max}$$$, где $$$P_{min}$$$ — минимальное значение $$$P$$$ среди баннеров в блоке, $$$P_{max}$$$ — максимальное, $$$len(Block_{s})$$$ — количество баннеров в блоке, $$$s$$$ — номер блока в разбиении. Значением метрики для конкретного разбиения является сумма значений $$$f$$$ для всех блоков в этом разбиении. На каждом запросе необходимо находить разбиение, которое максимизирует эту метрику.

Виталик умеет решать эту задачу, но его алгоритм оказался не очень быстрым. Вас, как эксперта, попросили помочь ему и ускорить отбор!

В распределённых системах одна из наиболее важных задач — это умение переживать сбои оборудования. Классическим подходом к решению проблемы сбоев в случае хранения данных является тройная репликация, то есть хранение каждого блока данных на трёх разных хостах в кластере. В таком случае данные не потеряются при одновременном выходе из строя двух дисков. Одновременная поломка трёх дисков считается крайне маловероятным событием и на практике практически никогда не случается.

Однако, тройная репликация приводит к тому, что для хранения $$$X$$$ данных на кластере надо иметь $$$3X$$$ свободного места, что достаточно расточительно. Для экономии места и сохранения гарантий надёжности используются коды, исправляющие ошибки (а точнее, в нашем случае, коды, исправляющие потерю части данных).

Рассмотрим один из таких кодов. Представим, что наши данные состоят из числа битов, кратного 20. Для простоты будем считать, что ровно из 20 бит и научимся кодировать эти 20 бит (для большего числа бит задача решается простым повторением данного алгоритма).

Итак, представим наши 20 бит в виде матрицы $$$\{a_{i,j}\}$$$ размером 4 на 5, то есть $$$i = 1 \ldots 4, j=1 \ldots 5$$$. Мы дополним матрицу с данными двумя контрольными столбцами $$$\{a_{i,6}\}$$$ и $$$\{a_{i,7}\}$$$.

Шестой столбец будет просто представлять собой xor-сумму столбцов, то есть: $$$$$$ a_{i,6} = \bigoplus_{j=1}^{5} a_{i,j}, \quad i = 1\ldots4 $$$$$$

Седьмой столбец будет устроен более хитро. Он будет представлять собой определённые xor-суммы диагоналей. А именно, положим $$$S=\bigoplus_{k=1..4} a_{k,6-k}$$$ , тогда: $$$$$$ a_{i,7} = S \oplus \bigoplus_{k=1..4} a_{k, shift(6 + i - k)}, \quad i = 1\ldots4 $$$$$$

Здесь $$$shift$$$ обозначает функцию, которая шагом величины 5 сдвигает число в диапазон $$$1 \ldots 5$$$, (то есть $$$shift(x) \in \{1 \ldots 5\}$$$ и $$$x - shift(x)$$$ кратно 5).

Изобразим вклад элементов в контрольные суммы 7-го столбца в виде матрицы: $$$$$$ \begin{pmatrix} a_{7,1} & a_{7,2} & a_{7,3} & a_{7,4} & S \\ a_{7,2} & a_{7,3} & a_{7,4} & S & a_{7,1}\\ a_{7,3} & a_{7,4} & S & a_{7,1} & a_{7,2} \\ a_{7,4} & S & a_{7,1} & a_{7,2} & a_{7,3} \end{pmatrix} $$$$$$

После этого мы будем писать каждый столбец матрицы на отдельный хост. Утверждается, что при потере любых двух столбцов их можно восстановить из имеющихся, то есть полученный код в определённом смысле не менее надёжен, чем тройная репликация. При этом видно, что накладные расходы указанного кода составляют лишь 40%, в отличие от 200%, которые были у тройной репликации.

Заметим, что при подсчёте контрольных сумм используется только операция xor, поэтому можно в качестве $$$a_{i,j}$$$ использовать числа фиксированной битовой ширины, а не просто биты. В нашем случае мы будем кодировать 32-битные беззнаковые числа.

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

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

В $$$n$$$ кластерах расположены сервера, на каждом из которых установлена одна и та же операционная система. В её ядре была найдена уязвимость, поэтому сервера нужно обновить на исправленную версию ядра. В $$$i$$$-м кластере расположено $$$x_i$$$ серверов. Обновление одного сервера занимает одну единицу времени. Сервера обновляются строго последовательно, поэтому их суммарное время обновления занимает $$$x_i$$$ единиц времени. Начатый процесс обновления в одном кластере нельзя прерывать до того, как все сервера в нём будут обновлены. Также нельзя выполнять обновление в двух кластерах одновременно. В каждом кластере под обновление было выделено окно времени $$$[a_i, a_i + x_i]$$$, эти окна могут пересекаться. Необходимо выбрать кластера, в которых провести обновление, чтобы на максимальном количестве серверов была установлена новая версия ядра.

У разработчика была директория $$$A$$$, в которой размещались директории и файлы. Для каждого файла посчитана его хэш сумма. В процессе работы известно, что разработчик создавал хардлинки, удалял хардлинки, создавал и удалял директории. Более формально, изменения были одного из четырех типов:

1. mkdir /some/dir/ — создать директорию с именем /some/dir/ в директории $$$A$$$.
2. rmdir /some/dir/ — удалить директорию с именем /some/dir/ в директории $$$A$$$.
3. unlink /some/file — удалить хардлинку с именем /some/file в директории $$$A$$$.
4. link /from/file /to/file — создать хардлинку с именем /to/file на /from/file в директории $$$A$$$. Тогда хэш сумма файла /to/file будет совпадать с хэш суммой файла /from/file.

При каждом изменении разработчик соблюдал правила:

1. Нельзя создавать новые файлы, только хардлинки.
2. Нельзя изменять файлы и директории вне директории $$$A$$$.
3. Новые хардлинки можно создавать только на существующие в $$$A$$$ файлы.
4. Можно удалять только пустые директории.
5. Нельзя создавать хардлинку в директории, которой не существует.
6. Нельзя создавать поддиректорию в директории, которой не существует.

В результате своей работы разработчик пришел к выводу, что это уже не директория $$$A$$$, а директория $$$B$$$. Тогда он решил рассмотреть все свои изменения от изначального состояния директории $$$A$$$ (далее просто "от $$$A$$$") до нынешнего состояния (далее "до $$$B$$$"). Но, к сожалению, он не смог найти историю изменений. Зато он смог найти список файлов с их хэш суммами и поддиректорий директории $$$A$$$ и список файлов с их хэш суммами и поддиректорий директории $$$B$$$.

Разработчик заметил, что пространства имен директорий в $$$A$$$ и файлов в $$$B$$$ не пересекаются, то есть нет файла в $$$B$$$ с именем, совпадающим с именем какой-либо директории в $$$A$$$. Аналогично, пространства имен файлов в $$$A$$$ и директорий в $$$B$$$ тоже не пересекаются, то есть нет файла в $$$A$$$ с именем, совпадающим с именем какой-либо директории в $$$B$$$. К тому же, если в $$$A$$$ и в $$$B$$$ есть файлы с одинаковым именем, то их хэш суммы тоже одинаковые.

Разработчик хотел бы восстановить последовательность своих изменений, соответствующих всем описанным правилам, но это невозможно, поэтому он просит Вас помочь найти произвольную минимальную последовательность.

Найдите минимальную последовательность изменений, соответствующих описанным правилам, которая преобразует директорию $$$A$$$ в директорию $$$B$$$.

Сеть компании состоит из серверов, каждый из которых имеет уникальный целочисленный идентификатор. $$$N$$$ пар серверов соединены друг с другом. Соединённые серверы образуют кластеры: два сервера относятся к одному и тому же кластеру, если от одного из них можно добраться до другого, перемещаясь по связям.

Периодически возникает необходимость скачать определённый файл на некоторый сервер. В сети работает сервис, аналогичный торрент-трекеру, который может сообщить, на каких серверах уже имеется необходимый файл.

Проблема, однако, заключается в том, что любой сервер может скачивать файлы только с серверов в его кластере.

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

Метаданные пользователей Яндекс.Почты лежат в БД PostgreSQL и разбиты на $$$N$$$ шардов (теоретически $$$N$$$ может быть очень большим). У каждого шарда есть вес, который постоянно пересчитывается пропорционально загрузке процессора на мастере шарда. Новому пользователю при регистрации автоматически присваивается шард рандомно с учётом веса этого шарда. Нужно реализовать класс который хранит веса шардов и отвечает на следующие типы запросов:

1. Обновить вес какого-то шарда.
2. Получить по заданному $$$weight$$$ номер шарда $$$i$$$ такого, что сумма весов шардов c номерами, находящимися на отрезке $$$[0, i]$$$ меньше или равна заданному весу, а сумма весов шардов c номерами, находящимися на отрезке $$$[0, i + 1]$$$ строго больше. Если сумма весов всех шардов не превосходит заданный вес, нужно вывести $$$n - 1$$$. Если вес нулевого шарда больше, чем $$$weight$$$, то надо вывести $$$-1$$$.

Индустриализация добралась до самых отдалённых уголков страны, и наружная реклама уже вовсю показывается в Байтландии.

Реклама на билбордах показывается по определённым правилам:

• каждый рекламодатель назначает ставку, которую он готов заплатить за своё объявление;
• в момент предполагаемого показа определяется список рекламных объявлений, готовых показаться на билборде, который находится в определённой точке;
• RTB-система (Real-time bidding) проводит аукцион второй цены между всеми объявлениями.

Аукцион второй цены проходит по следующей схеме:

• отсеиваются объявления, которые не готовы заплатить не менее минимальной ставки $$$MinCost$$$;
• рекламные объявления сортируются по убыванию ставок;
• первое объявление назначается победителем;
• со счёта рекламодателя списывается ставка второго объявления или $$$MinCost$$$, если объявление в аукционе одно.
• если есть несколько объявлений с максимальной ставкой $$$Cost$$$, то победитель из них выбирается случайно; в таком случае с рекламодателя списывается $$$Cost$$$.

Одной из новинок в индустрии рекламы является геотаргетинг — возможность задать окружность на карте, ограничивающую множество щитов, на которых необходимо производить рекламные показы конкретного объявления. Волевым решением Байтландия была выбрана в качестве испытательного полигона для новой функциональности. Перед аналитиком Михаилом стоит задача: определить места в городе, в которых рекламодатели готовы заплатить наибольшее количество денег. Для этого Михаил прикрепил огромный билборд на свой автомобиль и решил проехать по прямой улице из точки $$$(X_{start}, Y_{start})$$$. Автомобиль Михаила может ехать только с постоянной скоростью. В некоторые моменты времени аналитик останавливается и проверяет, какая реклама показывается на его билборде.

Помогите аналитику Михаилу определить лучшие места для расположения билбордов.

У вас есть записанный в строку невалидный json. Заранее известно что в нём был потерян один символ. Надо восстановить json до валидного добавив один символ. Об исходном JSON сообщении нам известно:

1. json или строка или словарь.
2. Словарь состоит из пар ключ значение разделенных двоеточием, следующая пара отделяется запятой.
3. Ключ словаря всегда строка. Уникальность ключей не требуется. Значение может быть строкой или словарем.
4. Строки выделяются только двойными кавычками ".
5. Строки не бывают пустыми и состоят только из символов [a-zA-Z0-9].
6. Словарь может быть пустым.
7. Пробелы отсутствуют.

Электронное письмо можно упрощённо представить в виде структуры

struct Message {
    int userId; // id получателя
    string from; // email-адрес отправителя
    unsigned receiveTimestamp; // время получения
    int folderId; // id папки, в которую доставлено письмо
    int threadId; // id цепочки (треда), в которую группируются письма при обсуждении
};

Нужно реализовать хранилище писем, в которое можно складывать письма и у которого можно запрашивать список писем по параметрам. Параметрами для запроса являются:

1. id юзера $$$userId$$$
2. id папки $$$folderId$$$
3. отрезок времени получения письма $$$[since, till]$$$, включительно
4. максимальное количество элементов в выдаче $$$count$$$

Письма в выдаче должны быть сгруппированы в треды (сначала идут письма первого треда, затем второго и так далее). Таймстемпом треда считается таймстемп самого свежего письма в этом треде.

Должны выбираться только треды, принадлежащие папке $$$folderId$$$. Считается, что тред принадлежит папке $$$folderId$$$, если хотя бы одно письмо из этого треда лежит в папке $$$folderId$$$. Таким образом в выдаче писем могут присутствовать письма с $$$folderId$$$, отличающимся от переданного.

В выдачу должны попасть только треды, таймстемпы которых попадают в отрезок $$$[since, till]$$$, включительно.

Треды в выдаче должны быть отсортированы по убыванию своих таймстемпов. Для тредов с одинаковым таймстемпом сортировка идет по увеличению $$$threadId$$$. Письма внутри треда должны быть отсортированы по убыванию таймстемпа. Для писем с одинаковым таймстемпом сортировка идет по порядку сохранения в хранилище.

После всех группировок применяется правило для ограничения количества элементов в выдаче: надо выбрать $$$count$$$ первых.

При решении различных задач используются классификационные алгоритмы (или классификаторы), которые относят наблюдаемый объект к определённому классу. Например, рассмотрим запросные классификаторы, которые относят запрос пользователя в поисковую систему к той или иной группе запросов: спортивные события, новости, рецепты и пр. Такие классификаторы помогают улучшить взаимодействие пользователя с сервисом.

При внедрении классификаторов смотрят на метрики и на время работы. Метрики отвечают за пользу, которую классификаторы приносят сервису, а время работы должно быть небольшим — для удобства пользователя. Опытным путём было выявлено, что для быстрого и комфортного взаимодействия с поисковой системой, одновременно может работать не более $$$M$$$ классификаторов.

Всего есть $$$K$$$ метрик, которые определены для каждого классификатора. Для набора классификаторов значение метрики определяется как максимум по ней среди классификаторов, входящих в набор. Пользой набора классификаторов считается сумма его метрик.

Вам дано $$$N$$$ классификаторов. Необходимо найти набор из $$$M$$$ классификаторов с максимальной пользой.