ЛКШ.2016.Август.A'

Строка компиляции g++: -Wall -Wextra -Werror -O2 -std=gnu++11 -static -lm -Wno-unused-result -Wno-deprecated-declarations -Wno-sign-compare
Вопросы к теоретическому зачету
Elephants statements, 100% original

Сводная таблица

Краткое содержание лекций
День 1: Условия Вход Таблица результатов
Алгоритмы на графах
  • Дфс, времена входа и выхода, функция up
  • Отсутствие перекрестных рёбер
  • Мосты
  • Точки сочленения
  • Компоненты реберной двусвязности
  • Компоненты вершинной двусвязности
  • СНМ
  • Лемма о безопасном ребре
  • Краскал
День 2: Условия Вход Таблица результатов
Паросочетание и Эйлеров цикл
  • Двудольные графы, проверка на двудольность
  • Паросочетание, теорема о дополняющей цепи
  • Алгоритм Куна
  • Вершинное покрытие и независимое множество в двудольных графах
  • Эйлеров цикл
День 3: Условия Вход Таблица результатов
Задачи о рюкзаке
  • Постановка задачи
  • ЗОРП
  • Решение с линейной памятью без восст. ответа
  • Случай без стоимостей. Битовое сжатие
  • Случай без стоимостей. Восстановление ответа с линейной памятью
  • ЗОРТ
  • Большое C
  • Случай без стоимостей. Поиск кратчайшего пути в графе остатков
  • Решение с помощью Meet-in-the-middle
  • Генерация в подмножеств с ценой в отсотрированном порядке за O(2^n)
  • Рюкзак в задачах на дереве
День 4: Условия Вход Таблица результатов
ДП со сложным состоянием
  • Состояние - подмножество
  • Пример - гамильтонов путь, комивояжер
  • Перебор всех подмножеств за O(3^n)
  • Состояние - профиль
  • Изломанный профиль
  • Пример - симпатичные узоры, замощения
  • Возведение матрицы в степень
  • Профиль - скобочная последовательность
  • Профиль - компонента связности
День 5: Условия Вход Таблица результатов
log(n) в геометрии
  • Выпуклая оболочка. Грэхем
  • Точка внутри выпуклого многоугольника.
  • Двоичный поиск на циклических последовательностях
  • Касательная к многоугольнику. Пересечения прямой и вып. многоульника
  • Калиперы. Минимальный и максимальный объемляющий прямоугольник.
  • Две наиболее удалённые точки
День 6: Условия Вход Таблица результатов
Разделяй и властвуй
  • Общий принцип разделяй и властвуй, примеры
  • Две самые ближние точки
  • Максимальный тандемный повтор
  • Dynamic connectivity offline
  • (*) Алгоритм Карацубы
День 7: Условия Вход Таблица результатов
ScanLine
  • Краткое напоминание про ДО, групповые операции
  • Сканирующая прямая
  • Число точек в прямоугольнике
  • Точка, накрытая макс. числом прямоугольников
  • Число самопересечений ломаной
  • Площадь объединения
  • Какая-нибудь точка пересечения отрезков (smoking)
  • Напоминание о декартовом дереве
День 8: Условия Вход Таблица результатов
Корневая эвристика
  • Разбить элементы на кусочки по sqrt(n)
  • Разбить запросы на кусочки по sqrt(n)
  • Перестраивать через sqrt(n) запросов
  • Если сумма объектов n, то различных <= sqrt(n)
  • Алгоритм Мо
  • Дискретный логарифм (Baby step Giant step)
День 9: Условия Вход Таблица результатов
Хеши, бор
  • Хеши подстрок
  • Сравнение строк, Суффиксный массив за O(n log^2 n)
  • Антихеш тест
  • Парадокc дней рождения
  • Выбор числа модулей, умножение чисел по модулю порядка sqrt(2) * 2^61
  • Хеши для множеств
  • Бор, хранение, применение
  • Цифровой бор
День 10: Условия Вход Таблица результатов
Ахо-Корасик
  • Префикс-функция
  • Автомат КМП
  • Постановка задачи
  • Суффиксные ссылки
  • Дополнение до автомата
  • Супер-суффиксные ссылки
  • Использование
День 11: Условия Вход Таблица результатов
Суффиксный массив
  • Определение
  • Построение за nlogn
  • Алгоритм Аримуры-Арикавы-Касаи-Ли-Парка
  • Применения
День 12: Условия Вход Таблица результатов
LCA
  • Постановка задачи
  • Двоичные подъёмы
  • Эйлеровы обходы деревьев
  • Сведение к RMQ
  • Sparse table
  • Level ancestor problem
  • Longest path decomposition (ladder)
  • LA O(nlogn), O(1) combo: ladder + jump-pointers
  • Алгоритм Тарьяна
День 13: Условия Вход Таблица результатов

Сервис от Никиты

Стена кода

void algorithmArimuriArihaviKasaiLiParka(vector &s) {
procedure swap(Var a, b : longint);
begin
  a := a xor b;
  b := a xor b;
  a := a xor b;
end;
void print(vector < int > &tree)
{
    printf("             %d              \n", tree[1]);
    printf("     %d              %d      \n", tree[2], tree[3]);
    printf("  %d      %d      %d      %d  \n", tree[4], tree[5], tree[6], tree[7]);
}
void func(int qwer)
const long long INF = 9223372036854775807;
nn = 1LL << (int)(log(k) / log(2) + 0.99999);
void Super_Puper_Mega_Merge(int v, int u){
vector> matrix5 = {
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1},
  {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
  {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1},
  {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
  {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1},
  {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};

Код от Коли

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int next_side[6][4] = {
{3, 4, 1, 2},
{0, 4, 5, 2},
{3, 0, 1, 5},
{5, 4, 0, 2},
{3, 5, 1, 0},
{1, 4, 3, 2}};

int add_rot[6][6] = {
{0, 0, 0, 0, 0, 0},
{0, 0, -1, 0, 1, 0},
{0, 1, 0, -1, 0, -2},
{0, 0, 1, 0, -1, 0},
{0, -1, 0, 1, 0, 2},
{0, 0, 2, 0, -2, 0}};
bool cmp(tuple t1, tuple t2) {
    if (get<0>(t1) != get<0>(t2)) {
        return get<0>(t1) < get<0>(t2);
    }
    if (get<2>(t1) != get<2>(t2)) {
        return get<2>(t1) < get<2>(t2);
    }
    if (get<1>(t1) != get<1>(t2)) {
        return get<1>(t1) < get<1>(t2);
    }     
    assert(false);
}
splitZero(root, root, VERYVERYVERYTEMP); // На самом деле, это код не мой, а моего сокомандника.
arrx.puba(x1);
arrx.puba(x2);
arry.puba(y1);
arry.puba(y2);
arrz.puba(z1);
arrz.puba(z2);
points[x1].puba({y1, z1});
points[x1].puba({y1, z2});
points[x1].puba({y2, z1});
points[x1].puba({y2, z2});
points[x2].puba({y1, z1});
points[x2].puba({y1, z2});
points[x2].puba({y2, z1});
points[x2].puba({y2, z2});
rects[x1].puba({{y1, z1}, {y2, z2}});
vector <tuple<plane, point3d, point3d, point3d>> gen_planes() {
    point3d q = a + b - a + c - a + d - a;
    point3d x = a + b - a + c - a;
    point3d y = a + b - a + d - a;
    point3d z = a + c - a + d - a;
    vector <tuple<plane, point3d, point3d, point3d>> pl = {make_tuple(plane(a, b, c), a, b - a, c - a), 
                                                           make_tuple(plane(a, b, d), a, b - a, d - a), 
                                                           make_tuple(plane(a, c, d), a, c - a, d - a), 
                                                           make_tuple(plane(q, x, y), q, x - q, y - q), 
                                                           make_tuple(plane(q, x, z), q, x - q, z - q), 
                                                           make_tuple(plane(q, y, z), q, y - q, z - q)};
    return pl;
}