\documentclass[12pt]{article}

% Конспект первой лекции
% Автор: Сергей Копелиович

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{hologo}
\usepackage{enumerate}
%\usepackage{color}
\usepackage{picture}

\voffset=-20mm
\textheight=220mm

\hoffset=-20mm
\textwidth=175mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}

\newcommand\Label[1]{\item {\bf #1}}
\def\Begin{$\bullet$\hspace{0.5em}}

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\newlength{\myskip}
\setlength{\myskip}{0.5em}

\newcommand\URL[1]{{\footnotesize{\url{#1}}}}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#1}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: вступительная лекция, разбор вступительного теста} \\
  \vspace{0.5em}
  {\Large 2 сентября} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\vspace{1em}
\tableofcontents
\pagebreak

\section{Общая информация по курсу}

\begin{itemize}
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{8pt}
  \Label{Преподаватель}: Сергей Владимирович Копелиович 
  \Label{Способы связи}: \\
    \Begin vk.com/burunduk1 (быстрое общение, постоянный контакт)  \\
    \Begin burunduk30@gmail.com (деловая переписка по учебе, сдача домашних заданий)  \\
    \Begin телефон: +7-921-331-99-56 
  \Label{Dropbox}: \URL{https://www.dropbox.com/sh/mh48b3jjv0roi4p/AAA58cpLM6tYNZV4y3YHjjHea?dl=0} 
  \Label{Тестирующая система}: \URL{http://acm.math.spbu.ru/tsweb/} 
  \Label{ACM}: тренировки по субботам в СПБ АУ, c 10:00 до 15:00, затем обед и разбор. \\
  Более подробная информация здесь \URL{http://acm.math.spbu.ru/~sk1/mm/au/2014/} 
  \Label{Язык программирования}: на этом курсе наш язык \t{C/C++} с \t{STL}. 
  \Label{Источники информации}:  \\
    \Begin wiki, вики, \URL{http://e-maxx.ru}, \URL{http://neerc.ifmo.ru/wiki}, отдельные статьи на хабре \\
    \Begin Книги: Кормен; Бабенко и Левин; Дасгупта и Вазирани. 
  \Label{Отчетность}: \\
    \Begin Одна глава электронного конспекта в \hologo{LaTeX}. Дедлайн 2 недели. \\
    \Begin Теорэкзамен общий с базовым курсом. \\
    \Begin Допуск к экзамену: зачет по практической части курса. \\
    \Begin Практическая часть: каждую неделю получаете контест и теорзадачи. \\
    \Begin Реализация и тестирование одного из описанных алгоритмов. С codereview, c промежуточным дедлайном 2 недели и окончательным дедлайном 1 месяц. \\
    \Begin Будет необязательно задание по гуглению. Вопросы из серии: за какое оптимальное время умеют решать задачу о maximum weighted matching?
\end{itemize}

\section{Общие слова про время работы, про тестирование}

\begin{itemize}
  \item Если вы знаете в теории некоторый алгоритм, но не понимаете, как его реализовать, знание менее ценно.
  \item Если вы реализовали алгоритм, а он работает ``не всегда'', такая реализация никому не нужна. Алгоритм должен на всех возможных случаях работать корректно.
  \item Если вы хотя бы один раз самостоятельно реализовали алгоритм, знание осядет глубже, надолго. 
        Во время реализации нового алгоритма вы убедитесь, что алгоритм понимаете до конца, и,
        скорее всего, встретите пару тонких моментов, о которых до этого не задумывались.
  \item Реализация может быть ``доказательством корректности''. Для этого в код нужно вставить побольше \t{assert}-ов,
        то есть, проверок утверждений, которые заведомо должны быть верными.
        Например, можно насчитать число сравнений, сделанных алгоритмом \t{MergeSort} и проверить
        в конце, что \\ это значение не больше $n \log_2 n$ \mbox{(\t{assert(cnt <= n*log(n)/log(2));})}.
        Кроме этого код следует протестировать на случайных тестах (случайная перестановка, $n$ случайных чисел от $1$ до $m$),
        на крайних случаях (все числа в массиве равны, тождественная перестановка, обратная перестановка).
        Если вы придумали новый сложный алгоритм, даже если есть проверенное письменное доказательство, рекомендуется алгоритм реализовать и протестировать,
        могут обнаружиться спецэффекты.
  \item Пусть вы поняли алгоритм, но не уверены, что до конца в нем разобрались. Есть два хороших способа проверить наверняка "---
        реализовать алгоритм, или, что обычно быстрее, запустить его руками (на бумажке) на небольшом тесте.
  \item Если вы думаете, что поняли алгоритм, вас просят его реализовать, а вы говорите, что за час не справитесь, значит,
        или это очень-очень сложный алгоритм, или вы поняли максимум общую идею, но не весь алгоритм, все его этапы и случаи.
  \item Современные машины делают ${\approx}10^9$ элементарных операций в секунду.
        Это значит, что не ``элементарных'' операций, например, \t{a[b[i]] = k++;} за секунду мы успеем сделать ${\approx}10^8$
        (здесь ошибка может быть в $2-3$ раза в обе стороны).
        По алгоритму и размеру данных нужно уметь быстро оценивать, насколько алгоритм быстро сработает. \\
        Пример \t{\#}1: за сколько вычисляется 20-е число Фибоначчи рекурсивной функцикей? $f_{20} \le 2^{20}$, значит мгновенно, сильно быстрее одной десятой секунды.\\
        Пример \t{\#}2: за сколько сортируется массив из $10^7$ элементов? $10^7 \log 10^7 \approx 240\cdot 10^6$, значит, около одной секунды
        (здесь может быть ошибка в несколько раз, но порядок мы оценили). 
  \item При вычислении времени работы полезно умение быстро переводить из двоичной в десятичную.
        $10^3 \approx 1024 = 2^{10} \SO 10^9 \approx 2^{30}$ и $10^8 \approx 2^{20} \cdot 100 \approx 2^{26}$.
\end{itemize}

\section{Оценка качества алгоритма}

При сравнение алгоритмов используется несколько критериев:
\begin{itemize}
  \item Время работы. Обычно это сложный фактор, нужно оценивать:
     \begin{MyList}
       \item Время выполнения в секундах на макс-тесте. До реализации оценивать сложно.
       \item Асимптотику. Но не всегда этого достаточно: \\ хеш-таблица, умножение матриц за $\O(n^{2.37})$.
       \item Константу. Количество операций: $10n$ определенно хуже, чем $2n$.
       \item Тип операций: хеш-таблица работает долго не из-за того что операций много. 
       \item При детальном анализе алгоритмов конкретного типа, например сортировок, отдельно оценивают число сравнений, число присваиваний и т.д.
             Так как в разных случаях нужны бывают разные сортировки. Примеры: суффиксный массив за $\O(n \log^2n)$, сортировка $100GB$ файла на жестком диске.
     \end{MyList}
   \item Количество использованной дополнительной памяти (размер входных данных не считается, иногда также не учитывается размер выходных данных).
         Память считается более дорогим, чем время, ресурсом. 
   \item Возможность распараллеливания на несколько машин. Это относится особенно к структурам данных.
   \item Поведение алгоритма можно оценивать в худшем случае, в среднем случае (матожидание по входным данным), в лучшем случае.
         Если алгоритм вероятностный, как \t{QuickSort}, можно оценивать матожидание по случайным битам.
   \item Количество крайних случаев. Это особенно видно на геометрических алгоритмах. Вот примеры задач,
         идея решения которых несложна, но умение реализовать эти идеи считается серьезным мастерством.
     \begin{MyList}
       \item Является ли диагональ невыпуклого многоугольника нестрого внутренней? $\O(n)$
       \item Найти длину пересечения прямой и невыпуклого многоугольника. $\O(n)$
       \item Найти площадь пересечения двух невыпуклых многоугольников. $\O(n^2\log n)$
       \item Получение планарного графа, представляющего собой объединение/пересечение $k$ невыпуклых многоугольников. $\O(n^2\log n)$
       \item Построение диаграммы Вороного в 2D за $\O(n \log n)$ методом заметающей прямой.
     \end{MyList}
         Если вы придумали новый алгоритм и в нем масса крайних случаев, пожалуйста, не спешите публиковаться, не плодите ад!
   \item Длина кода (LOC = lines of code) и сложность идеи.
         Опытнам программистам может показаться, что это не так важно "--- один раз написал, сто лет работает, все пользуются и рады.
         Но если сложным и длинным в реализации алгоритмом начинают пользоваться как черным ящиком,
         часто нет возможности модифицировать алгоритм изнутри для решения схожих задач.
         Также бывает, что из-за повышенной сложности алгоритма кроме очень узкого круга спецалистов никто до конца не знает,
         как же это все работает, в итоге тема не развивается, а иногда даже забывается.
   \item Число проходов по входным данным. Однопроходные алгоритмы.
   \item Online/Offline структуры данных (см. следующую лекцию).
   \item Амортизированное, real time время работы (см. следующую лекцию).
\end{itemize}

\section{Разбор теста}

\newcommand{\Item}[1]{\item {\bf Задача \t{\##1}.}}
\begin{itemize}
  \Item{1} \\
    (a) $O(n^2)$ "--- сортировка вставками, выбором, пузырьком \\
    (a) $O(n \log n)$ "--- merge sort, quick sort, heap sort \\
    (b) $O(n + m)$ "--- сортировка подсчетом. 
        \texttt{\begin{MyList}
          \item \hspace{0em} int cnt[M]; // заполнен нулями
          \item \hspace{0em} for (i = 0; i < n; i++) // O(n)
          \item \hspace{2em}   cnt[a[i]] += 1;
          \item \hspace{0em} for (i = 0; i < m; i++) // O(m)
          \item \hspace{2em}   for (j = 0; j < cnt[i]; j++) // O(n) в сумме по всем i 
          \item \hspace{4em}     print(i); // выводим cnt[i] раз число i 
        \end{MyList}}
    (b) $O(n), O(m)$ "--- формально не верно, правильно $O(n + m)$. \\
    (b) $O(n + n\log_n{m})$ "--- цифровая сортировка (radix sort, digital sort). \\
    (b) Дополнительные баллы всем, кто вспомнил про длинные числа.
  \Item{2} \\
     (a) Дек, реализация на массиве, $\O(1)$ \\
     (b) Массив, $\O(1)$ \\
     \mbox{}\hspace{1em} \t{i = rand() \% n; swap(a[i], a[n-1]); return a[-{}-n];} \\
     (c) Куча с обратными ссылками \t{+} массив, $\O(\log n)$ \\
     \mbox{}\hspace{1em} \t{Node p[]; p[i]} "--- позиция в куче элемента, добавленного в $i$-й момент времени \\
     (d) Двусвязный список + массив, $\O(1)$ \\
     \mbox{}\hspace{1em} \t{Node p[]; p[i]} "--- позиция в списке элемента, добавленного в $i$-й момент времени \\
     (e) HashMap, рандомизированное $\O(1)$ \\
     (f) куча с обратными ссылками \t{+} HashMap, $\O(\log n)$ \\
     \mbox{}\hspace{1em} \t{HashMap<int,Node> p;} "--- по элементу за $\O(1)$ узнаем его позицию в куче.
  \Item{3а} 
     \texttt{\begin{MyList}
       \item \hspace{0em} max = a[0], result = 0;
       \item \hspace{0em} for (i = 1; i < n; i++) \{
       \item \hspace{2em}   if (a[i] + max >= S)
       \item \hspace{4em}     result = 1;
       \item \hspace{2em}   if (a[i] > max)
       \item \hspace{4em}     max = a[i];
       \item \hspace{0em} \}
     \end{MyList}}
  \Item{3б} \\ 
     Решение, за $\O(\sqrt{n})$:
     \texttt{\begin{MyList}
       \item \hspace{0em} for (a = 1; a * a <= n; a++) \{
       \item \hspace{2em}   b = sqrt(n - a * a);
       \item \hspace{2em}   res += (a * a + b * b == n);
       \item \hspace{0em} \}
     \end{MyList}}
     Решение, за $\O(\sqrt{n})$ элементарных арифметических операций с целыми числами:
     \texttt{\begin{MyList}
       \item \hspace{0em} for (a = 1, b = sqrt(n); a <= b; a++) \{
       \item \hspace{2em}   while ((tmp = a * a + b * b) > n) // $2\sqrt{n/2}$ умножений
       \item \hspace{4em}     -{}-b;
       \item \hspace{2em}   if (tmp == n)
       \item \hspace{4em}     res += (a == b ? 1 : 2);
       \item \hspace{0em} \}
     \end{MyList}}
  \Item{4а} \\ 
     Одна из возможных идей "--- предподсчет за $\O(n^2)$, можно положить все элементы 
     матрицы в хеш-таблицу и за $\O(1)$ отвечать на поступающие запросы.
     Если предподсчет запрещен, то на один запрос можно отвечать за время $\O(n)$:
     \texttt{\begin{MyList}
       \item \hspace{0em} i = n - 1, j = 0;
       \item \hspace{0em} while (i >= 0 \&{}\&{} j < n) \{
       \item \hspace{2em}   if (a[i][j] == x)
       \item \hspace{4em}     return 1;
       \item \hspace{2em}   (a[i][j] < x) ? ++j : -{}-i;
       \item \hspace{0em} \}
     \end{MyList}}
     Заметим, что без предподсчета быстрее чем за $\O(n)$ на запрос не ответить, так как 
     на побочной диагонали могут стоять произвольные числа.
  \Item{4б} \\ 
     Существуют решения за $\O(n)$, это или алгоритм Манакера (аналог $Z$-функции), или построение дерева палиндромов.
     Оба алгоритма просты в реализации и встретятся в курсе позднее.
     Дерево палиндромов также позволяет за $\O(n)$ решить задачу \t{\#8а} "--- число различных подстрок-палиндромов.
     Здесь описаны лишь более простые решения. Итак, решения за $\O(n^2)$ и $\O(n \log n)$:
     \begin{MyList}
       \item У каждого палиндрома есть центр. Центр находится или в позиции $i$, или между позициями $i$ и $(i+1)$. Центр можно перебрать.
       \item Решим задачу для фиксированного центра $x$. Если есть палиндром с центром в $x$ и длиной $L$, то есть и палиндромы с центром в $x$ и длинами
             $L-2, L-4, \dots$. Поэтому достаточно найти максимальное $L$. 
        \item Поиск максимального $L$ за линейное время: \t{while (s[x+L] == s[x-L]) L++;}
        \item Поиск максимального $L$ за $\O(\log n)$: бинарный поиск, а внутри сравнение подстрок за $\O(1)$ с помощью полиномиальных хешей.
     \end{MyList}
\end{itemize}

\section{Разбор задачи 8}

\begin{itemize}
  \Item{8а} \\ 
     Докажем, что в строке длины $n$ различных подстрок-палиндромов не более $n$.
     База индукции: в строке длины $1$ есть ровно $1$ подпалиндром.
     Шаг индукции: докажем для строки $s$ длины $n+1$, $s = wa, |w| = n$, для строки $w$ мы уже знаем, что различных подпалиндромов не более $n$.
     Рассмотрим все суффиксы $s$, являющиеся палиндромами. Самый длинный суффикс $z$ мог оказаться новым подпалиндромом, покажем, что любой
     более короткий суффикс-палиндром $u$ встречался, как подстрока, в строке $w$:

     \setlength{\unitlength}{0.8cm}
     \begin{picture}(6,1.5)
       \thicklines
       \put(0,1){\line(1,0){5}}
       \put(0,1.5){\line(1,0){5}}
       \put(0,1){\line(0,1){0.5}}
       \put(5,1){\line(0,1){0.5}}
       \put(5.2,1.1){$s$}

       \put(2,0.5){\line(1,0){3}}
       \put(2,0.5){\line(0,1){0.5}}
       \put(5,0.5){\line(0,1){0.5}}
       \put(5.2,0.6){$w$}

       \put(2,0){\line(1,0){1}}
       \put(2,0){\line(0,1){0.5}}
       \put(3,0){\line(0,1){0.5}}

       \put(3.3,0.1){$=$}

       \put(4,0){\line(1,0){1}}
       \put(4,0){\line(0,1){0.5}}
       \put(5,0){\line(0,1){0.5}}
       \put(5.2,0.1){$u$}
     \end{picture} \\
     Чтобы доказать равенство, мы пользуемся тем, что строки $w$ и $u$ "--- палиндромы.
  \Item{8б} \\ 
     Опишем решение за $1.38^n$.
     Рассмотрим произвольную вершину $v$, мы ее или возьмем в ответ, или не возьмем.
     Если возьмем, то мы не можем брать её соседей.
     Получаем рекурсивное решение, которое в первой ветке удаляет вершину $v$ и запускается
     от оставшейся части графа (не берёт $v$ в ответ), а во второй ветке удаляет вершину $v$ и всех
     её соседей, после чего запускается от остатка (берёт $v$ в ответ).
     Пусть в исходном графе $n$ вершин, тогда время работы нашего решения $T(n)$, можно
     оценить как $T(n) = T(n-1) + T(n-d-1)$, где $d$ "--- степень вершины $v$. 
     Чем $d$ больше, тем лучше. Осталось заметить, что если в графе присутствуют только вершины
     степени не более двух, то наш граф "--- набор путей и циклов, и максимальное независимое множество
     ищется на нем жадно. Получили $T(n) \le T(n-1) + T(n-4) \SO T(n) = \O(1.38^n)$.
\end{itemize}

\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\begin{center}
  \t{\Large{\bf КОНЕЦ}}
\end{center}

\end{document}
