Ввведение.

  1. Задача про сапера. Метод Гаусса? Нет, целочисленное линейное программирование.

Гаусс

  1. Метод Гаусса для поля за O(N3). Поле = R, C, Z/pZ. timus : 1042.
  2. Метод Гаусса по произвольному модулю M.
    1. Подсчет определителя. Алгоритм Евклида.
    2. Поиск решений. Лемма Гензеля и К.Т.О. 100922_A0 : arcade
  3. Вещественный метод Гаусса. Большая погрешность. Матрица Гильберта. 100922_A0 : game
  4. Проверка уравенения det A = 0 <=> проверка по большому простому модулю. Линейно независимые вектора.
  5. Not read Добавление вектора в набор за O(N2).
  6. Not read Линейно независимые вектора = матроид. Решение задачи timus : 1041.

Про простые числа

  1. Поиск обратного.
    1. Методом ap-2, aPhi(m)-1
    2. Методом x*a + y*m = 1, для любых (a,m) = 1.
    3. Преимущество последнего при больших a, m. Преимущество при непростых m.
  2. Поиск первообразной
    1. За O(N). Перебираем все, проверям за линию.
    2. За O(logN). Перебираем все, проверяем за O(числа различных простых делителей).
  3. Дискретное логарифмирование: решение ax = b (m)
    1. За O(N)
    2. За O(sqrt(N)*logN)

Meet-In-The-Middle

  1. Задачи про рюкзак.
    1. Решение задачи о разбиении на 2 кучки за O(n*2n/2)
    2. Та же задача, но посчитать число способов. 100922_A0 : knapsack
    3. Та же задача, но теперь можно некоторые предметы не брать. O(n*3n/2).
  2. Задачи про графы.
    1. Найти max подклику.
    2. Найти количество подклик (разобрано потом).
    3. Not read Выделить подграф с max E / V.

Задача о рюкзаке.

  1. Задача = набрать ровно W.
  2. Time = O(W*N), Memory = O(W), Восстановление ответа.
  3. Новая задача = набрать небольше W, но максимизировать ценность. Как восстанавливать ответ?
  4. Not read Методы оптимизации динамики Time=O(N2), Memory=O(N2) по памяти
    1. Not read Храним только последнюю строку, Memory=O(N), но не можем восстановить ответ.
    2. Not read Корневая эвристика. Memory=O(N3/2), можем восстановить ответ.
    3. Not read Двоичное дерево. Time=O(N2logN), Memory=O(N).
  5. Not read Новая задача = Каждой вещи у нас Ki штук.
    1. Not read Решение за O(WNlogW) с деревом отрезков.
    2. Not read Решение за O(WNlogK) дроблением каждого K на logK отдельных вещей.

Практика

  1. Контест 100922a0 (условия)