\documentclass[12pt]{extreport}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{indentfirst}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%% Enumerations %%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

%%%%%%%%%%%%%%%%%%%%% EOF Enumerations %%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}
\definecolor{Gray333}{HTML}{333333}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{prvar}

\def\beforPRskip{
	\bigskip
	%\vspace*{2ex}
}

\def\PRSUBskip{
	\medskip
}


\def\pr{\beforPRskip\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}}
\def\pru{\beforPRskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}}
\def\prstar{\beforPRskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.}\setcounter{subproblem}{0}\;}
\def\prpfrom[#1]{\beforPRskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0} }
\def\prp{\beforPRskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }

\def\prpvar{\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;$\langle${\rm\Rnum{\theprvar}}$\rangle$.}\setcounter{subproblem}{0}\;}
\def\prpv{\beforPRskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\beforPRskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}.\setcounter{subproblem}{0} }

\def\prpstar{\beforPRskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\beforPRskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0} }
\def\upr{\beforPRskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\PRSUBskip\noindent\stepcounter{subproblem}{\sf \thesubproblem .} }
\def\prsubr{\PRSUBskip\noindent\stepcounter{subproblem}{\bf \asbuk{subproblem})}\;}
\def\prsubstar{\PRSUBskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.  } }
\def\prsubrstar{\PRSUBskip\noindent\stepcounter{subproblem}{$\text{\bf \asbuk{subproblem}}^*\mathbf{)}$}\;}

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0}
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0}
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

\DeclareDocumentCommand{\Pr}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf\theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}


\def\prend{
	\bigskip
%	\bigskip
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%\usepackage{erewhon}
%\usepackage{heuristica}
%\usepackage{gentium}

\usepackage[portrait, top=3cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}

\usepackage[linesnumbered]{algorithm2e}   

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\lhead{\fontfamily{fca}\selectfont {Основные алгоритмы 2020} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
%\rhead{\fontfamily{fca}\selectfont Домашнее задание 2}
%\rhead{\small 01.09.2016}
\cfoot{}

\usepackage{titlesec}
\titleformat{\section}[block]{\Large\bfseries\filcenter {\setcounter{problem}{0}}  }{}{1em}{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Обозначения и операции %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                                                                    
\newcommand{\divisible}{\mathop{\raisebox{-2pt}{\vdots}}}           
\let\Om\Omega


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Shen Macroses %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\w}[1]{{\hbox{\texttt{#1}}}}

\usepackage{enumitem}

\begin{document}
	


\noindent\textbf{Преамбула.} Поскольку мы изучили хэш-таблицы, операции в которых стоят $O(1)$ за счёт использования вероятности, хотя в худшем случае это не так, в этом задании мы считаем, что когда требуется найти алгоритм со сложностью $O(f(n))$, операции с хэш-таблицами при их использовании стоят $O(1)$.

\pr В языке C++ структура данных \texttt{std::set} реализована с помощью красно-чёрных деревьев. В ней хранится множество ключей, при этом считается, что ключи упорядочены. Помимо стандартных операций (вставки, поиска, удаления), которые стоят $O(\log n)$, где $n$~"--- число элементов в структуре данных, эта структура данных позволяет вывести все элементы в отсортированном порядке за $O(n)$. Опишите, как модифицировать красно-чёрное дерево так, чтобы сделать возможным такой вывод и не изменить стоимость стандартных операций. Считайте, что балансировка дерева после добавления и удаления элемента стоит $O(\log n)$.

\medskip

Семейство хэш-функций $\H$ называется \emph{универсальным}, если для любых фиксированных различных $x$ и $y$ вероятность события $f(x)=f(y)$ равна $1/m$, где $f$ выбирается случайно и равновероятно из $\H$ и отображает $n$-элементное множество (пространтство ключей) в $m$-элементное множество.

\medskip


\pr Семейство хэш-функций $H = \{f,g,h\}$, отображающих множество ключей $\{0,1,2,3\}$ в множество хэшей $\{0,1,2\}$, задано таблицей. Является ли оно универсальным?

\medskip


\begin{tabular}{|c|c|c|c|}
\hline
ключи&значения $f$&значения $g$&значения $h$\\
\hline
0&0&1&0\\
\hline
1&0&2&2\\
\hline
2&1&2&2\\
\hline
3&1&1&0\\
\hline
\end{tabular}

\prend

\pr В структуре данных <<динамический массив>> (в C++ \texttt{std::vector}) удаление $k$-го элемента стоит $O(n-k)$, где $n$~"--- количество элементов в массиве. Это происходит за счёт сдвигов: необходимо, чтобы первый элемент динамического массива находился в первой ячейке выделенной под массив памяти, а также нужно, чтобы между соседними элементами не было пустых ячеек памяти. Поэтому после очищения $k$-ой ячейки в результате удаления требуется последовательно сдвинуть $n-k$ последних элементов на единицу влево.

Так, удаление последнего элемента стоит $O(1)$, поэтому с помощью динамических масивов стандартно реализует стеки, а удаление первого элемента стоит $O(n)$, поэтому использовать динамические массивы для наивной реализации очереди (при извлечении из очереди первый элемент извлекают из массива, а потом удаляют, а новые элементы добавляются в конец массива)~"--- не лучшее решение.

Однако, с помощью динамического массива можно эффективно реализовать очередь поплатившись двукратным увеличением памяти.% Пусть известно, что одновременное максимальное число элементов в очереди $n$.
 Как и в случае наивной реализации, элементы будут извлекаться из начала массива $A$, а добавляться будут в его конец. Заведём указатель (целочисленная перменная $b$), который сначала указывает на первый элемент массива ($b=0$). Когда требуется извлечь элемент из очереди, сам элемент физически удаляться не будет, а будет увеличиваться лишь указатель: при извлечении из очереди возвращается элемент $A[b]$, после чего $b$ увеличивается на единицу. В каждый момент, когда $b \geq \lfloor \frac{n}{2} \rfloor$ ($n$~"--- число элементов в массиве $A$), происходит удаление $b$ элементов из массива, после чего $b$ присваивается значение~$0$.
 
Уточните описанный выше алгоритм так, чтобы в результате $n$ любых запросов к структуре данных <<очередь>> выполнялось $O(n)$ операций и при этом выделяемая под динамический массив память не превосходила удвоенную память, требуемую для хранения очереди.

\textbf{Указание}. Для доказательства оценки используйте амортизационный анализ.

\prend

\pr Опишите реализацию структуры данных <<очередь с приоритетами>> (из классного листка) со следующими стоимостями операций 

\begin{itemize}
	\item \texttt{insert}~"--- $O(1)$,
		\item \texttt{extract\_max}~"--- $O(n)$, 	\item \texttt{set\_priority}~"--- $O(1)$. 
\end{itemize}

При этом известно, что все ключи~"--- уникальные числа в диапазоне от $1$ до $n$.

\prend

\pr \prsubinline Постройте оптимальный алгоритм, который находит минимальный элемент в куче на максимум.

\prsubinline Докажите, что ваш алгоритм оптимальный: если ваш алгоритм работает за время $O(f(n))$, то любой алгоритм работает за время $\Omega(f(n))$. Считайте, что алгоритм не знает элементы заранее, куча хранится в памяти как массив $a$ и алгоритм может за один запрос $i$ узнать элемент $a[i]$.

\prend

\pr Дан массив из $n+1$ элемента, который содержит элементы от $1$ до $n$ и известно, что каждое число от $1$ до $n$ встречается хотя бы один раз. 

\prsub Докажите, что какое-то число от $1$ до $n$ встречается два раза.

\prsub Предложите алгоритм, который находит дубликат за $O(n)$.

\prsub Предложите алгоритм, который находит дубликат за $O(n)$ и $O(1)$ дополнительной памяти.

\prend

\pr Постройте алгоритм, который получив на вход числовой массив выводит количество его подмассивов (непрерывных подпоследовтаельностей), в которых все элементы различны.


\prend

\pr Структура данных <<таблица>> представляет собой числовую матрицу размера $m\times n$ (двумерный массив), элементы которой в каждой строке и каждом столбце отсортированы по возрастанию. В случае, если в таблице меньше $mn$ элементов, в незаполненных клетках написано $\infty$.

\prsub Постройте алгоритм, который проверяет находит элемент $x$ в  частично заполненную таблицу за $O(m+n)$ или проверяет, что такого элемента в таблице нет.

\prsub Постройте алгоритм, вставляющий новый элемент в частично заполненную таблицу за $O(m+n)$.

\prsubstar Постройте алгоритм, удаляющий элемент из частично заполненной таблицы за $O(m+n)$.

\prend


\end{document}
  