Тренировки

Тренировка 02.11.13

ariacas
2 ноября 2013, 02:45

Начало в 12.30. Провожу я, Ренат Гимадеев, +79253802179, пишем уральский чф

4 комментария

Будет разбор? Интересны решения задач C и G

так же интересна ссылка для тех, кто не писал. )

ссылка таже, что и на прошлый контест

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

B. Нужно посчитать суммы max(0, a_i - k) и max (0, k - a_i)

C. Нужно хранить подвешенное дерево программ клонов и указателей их нахождения на них. Операция обучения - добавления ребра вперед, отмены добавляем -1 к текущими состоянию, +1 добавляем к текущиму состоянию, таким образом нужно уметь перемещаться на k вверх, это можно организовать храня шаги на 1,2,4,8... для каждой вершины

D. Нужно аккуратно переставить фразы не забывая про заглавную букву.

E. Прямолинейная динамика по n и k. (ans[n,k] хранит ответ, мы перебираем число исключенных сенаторов 1..n для максимизации ответа

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

G. Условие не очень понятно, но видимо хотелось найти такой отрезок который различается с заданным в наименьшем числе бит, а из таких самый правый, для этого можно развернуть вторую строку и перемножить строки как многочлены (с помощью ФФТ), а дальше найти ответ на задачу.

H. Надо найти полное паросочетание на двудольном графе с 1000 вершинами и 500000 ребер, проходов будет не более 500, так что успеет, учитывая особую структуру графа, должно вообще быстро работать.

I. Пройтись двумя указателями, для каждой позиции посчитать наимешьнший отрезок на котором сумма весов больше к, потом просто симулировать процесс, по событиям потери концентрации.

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