\documentclass[12pt]{article}

\usepackage{cmap}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{graphicx}
\usepackage{amsthm,amsmath,amssymb}
\usepackage[russian,colorlinks=true,urlcolor=red,linkcolor=blue]{hyperref}
\usepackage{enumerate}
\usepackage{datetime}
\usepackage{minted}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{color}
\usepackage{verbatim}
\usepackage{tikz}
\usepackage{epstopdf}
\usepackage{xifthen}
%\usepackage[shortlabels]{enumitem} % [shortlabels] -- чтобы работало вместе с {enumerate}

\def\NAME{Паросочетания}
\def\DATE{7 сентября}
\def\CURNO{\NO\t{1}}

\parskip=0em
\parindent=0em

\sloppy
\voffset=-20mm
\textheight=235mm
\hoffset=-25mm
\textwidth=180mm
\headsep=12pt
\footskip=20pt

\setcounter{page}{0}
\pagestyle{empty}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{brown}{rgb}{0.5,0.5,0}
\newcommand{\red}[1]{{\color{red}{#1}}}
\newcommand{\dkgreen}[1]{{\color{dkgreen}{#1}}}

% Отступы для списков
\newlength{\ShiftLength}\setlength{\ShiftLength}{1.8em}
\newcommand{\leftLabel}[2][]{%
  \ifthenelse{\equal{#1}{}}{%
    {\hspace*{-\ShiftLength}\makebox[0pt][r]{\color{black}{#2}}\hspace*{\ShiftLength}}%
  }{%
    {\hspace*{-\ShiftLength}\makebox[0pt][r]{\color{#1}{#2}}\hspace*{\ShiftLength}}%
  }%
}

% Основные математические символы
\DeclareSymbolFont{extraup}{U}{zavm}{m}{n}
\DeclareMathSymbol{\heart}{\mathalpha}{extraup}{86}
\newcommand{\N}{\mathbb{N}}   % Natural numbers
\newcommand{\R}{\mathbb{R}}   % Ratio numbers
\newcommand{\Z}{\mathbb{Z}}   % Integer numbers
\def\INF{\t{+}\infty}         % +inf
\def\EPS{\varepsilon}         %
\def\EMPTY{\varnothing}       %
\def\PHI{\varphi}             %
\def\SO{\Rightarrow}          % =>
\def\EQ{\Leftrightarrow}      % <=>
\def\t{\texttt}               % mono font
\def\c#1{{\rm\sc{#1}}}        % font for classes NP, SAT, etc
\def\O{\mathcal{O}}           %
\def\NO{\t{\#}}               % #
\renewcommand{\le}{\leqslant} % <=, beauty
\renewcommand{\ge}{\geqslant} % >=, beauty
\def\XOR{\text{ {\raisebox{-2pt}{\ensuremath{\Hat{}}}} }}
\newcommand{\q}[1]{\langle #1 \rangle}               % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}        %
\newcommand{\sfrac}[2]{{\scriptstyle\frac{#1}{#2}}}  % Очень маленькая дробь
\newcommand{\mfrac}[2]{{\textstyle\frac{#1}{#2}}}    % Небольшая дробь
\newcommand{\score}[1]{{\bf\color{red}{(#1)}}}

% Отступы
\def\makeparindent{\hspace*{\parindent}}
\def\up{\vspace*{-0.3em}}
\def\down{\vspace*{0.3em}}
\def\LINE{\vspace*{-1em}\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}}
%\def\up{\vspace*{-\baselineskip}}

\lhead{Алгоритмы, осень 2018/19}
\chead{}
\rhead{Практика \CURNO. \NAME.}
\renewcommand{\headrulewidth}{0.4pt}

\lfoot{}
\cfoot{\thepage\t{/}\pageref*{LastPage}}
\rfoot{}
\renewcommand{\footrulewidth}{0.4pt}

\newenvironment{MyList}[1][4pt]{
  \begin{enumerate}[1.]
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{#1}
}{       
  \end{enumerate}
}
\newenvironment{InnerMyList}[1][0pt]{
  \vspace*{-0.5em}
  \begin{enumerate}[a)]
  \setlength{\parskip}{#1}
  \setlength{\itemsep}{0pt}
}{
  \end{enumerate}
}

\newcommand{\Section}[1]{
  \refstepcounter{section}
  \addcontentsline{toc}{section}{\arabic{section}. #1} 
  %{\LARGE \bf \arabic{section}. #1} 
  {\LARGE \bf #1} 
  \vspace*{1em}
  \makeparindent\unskip
}
\newcommand{\Subsection}[1]{
  \refstepcounter{subsection}
  \addcontentsline{toc}{subsection}{\arabic{section}.\arabic{subsection}. #1} 
  {\Large \bf \arabic{section}.\arabic{subsection}. #1} 
  \vspace*{0.5em}
  \makeparindent\unskip
}

% Код с правильными отступами
\newenvironment{code}{
  \VerbatimEnvironment

  \vspace*{-0.5em}
  \begin{minted}{c}}{
  \end{minted}
  \vspace*{-0.5em}

}

% Формулы с правильными отступами
\newenvironment{smallformula}{
 
  \vspace*{-0.8em}
}{
  \vspace*{-1.2em}
  
}
\newenvironment{formula}{
 
  \vspace*{-0.4em}
}{
  \vspace*{-0.6em}
  
}

\begin{document}

\renewcommand{\dateseparator}{--}
\begin{center}
  {\Large\bf 
   Второй курс, осенний семестр 2018/19\\
   Практика по алгоритмам \CURNO\\
   \vspace*{0.5em} 
   \NAME \\
   \vspace*{0.5em} 
   \DATE}\\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\LINE
\vspace{1em}


\pagestyle{fancy}




%\pagebreak
%\input 180907-tutorial-hw.tex

\vspace*{0.5em}
\Section{Домашнее задание}

\Subsection{Обязательная часть}

\begin{MyList}[8pt]

  \item \score{1.5} {\bf Петя и гиперкуб}\\
    У маленького Пети любимая игрушка -- $d$-мерный гиперкубик ($d \le 10$).
    Некоторые вершины у куба белые, некоторые чёрные. Вы знаете цвета всех вершин,
    помогите Пете перекрасить как можно меньше белых вершин в красный цвет так,
    чтобы не было двух смежных по ребру белых вершин.


  \item \score{3} {\bf Лексмин вершинное покрытие}\\
    Дан двудольный граф. Среди всех вершинных покрытий минимального размера
    найти лексикографически минимальное.
    $\O(\c{poly}(V,E))$.
  
  \item \score{2\t{+}1} {\bf Разбиение на циклы}
    \down
    \begin{InnerMyList}
      \item \score{2} Разбейте вершины {\bf ор}графа на циклы. Каждая вершина должна быть покрыта ровно одним циклом.
        Либо скажите, что это невозможно.
      \item \score{1} Разбейте вершины {\bf ор}графа с весами на ребрах на циклы $\min$ суммарного веса.
        Либо скажите, что это невозможно.
    \end{InnerMyList}
  
  
  \item \score{3} {\bf Степень не более двух}\\
    Дан произвольный {\bf не}орграф. Найдите $\max$ по размеру мультимножество рёбер, такое,
    что степень каждой вершины $\le 2$. Любое ребро можно брать два раза.
  
  \item \score{3} {\bf Множество прямых}\\
    Дано $N$ различных прямых. Выбрать $\max$ по размеру подмножество прямых, такое, что
    никакие две прямые не параллельны, и никакие прямые не пересекаются в точке c $x=0$.

  \item \score{3} {\bf Быстрое паросочетание в регулярном графе}\\
    Дан $2^k$-регулярный граф. Найдите совершенное паросочетание за $\O(E)$ (детерминированным алгоритмом).

\end{MyList}

\pagebreak
\vspace*{0.5em}
\Subsection{Дополнительная часть}

\begin{MyList}[8pt]

  \item \score{3} {\bf Лексмин вершинное покрытие 2}\\
    Дан двудольный граф. Среди всех вершинных покрытий минимального размера
    найти лексикографически минимальное.
    $\O(VE)$.

  \item \score{3} {\bf Вершинно-взвешенное паросочетание}\\
    В двудольном графе у каждой вершины левой доли есть вес $a_i$.
    Вес ребра равен весу его конца из левой доли. Найдите паросочетание $\max$ веса за $\O(VE)$.\\
    {\it Правильное решение без доказательства оценивается в $1$ балл}.

  \item \score{4} {\bf Вершинно-взвешенное паросочетание-2}\\
    В двудольном графе у каждой вершины левой доли есть вес $a_i$, у каждой вершины правой вес $b_i$.
    Вес ребра равен сумме весов его концов. Найдите паросочетание $\max$ веса за $\O(VE)$.\\
    {\it Правильное решение без доказательства оценивается в $2$ балла}.

  \item \score{3} {\bf Чётность числа паросочетаний}\\
    Приведите полиномиальный алгоритм для нахождения чётности числа
    совершенных паросочетаний в двудольном графе с равным размером долей.

  \item {\bf Оптимизация Н}\\
    Рассмотрим такую оптимизацию Куна.
    \begin{code}
bool kuhn(int v) {
  for (int u : graph[v])
    if (!used[u]) {
      used[u] = true;
      if (right_pair[u] == 0 || kuhn(right_pair[u])) {
        right_pair[u] = v;
        used[u] = false;
        return true;
      }
    }
  return false;
}
...
fill(used.begin(), used.end(), false);
for (int v = 1; v <= n; ++v) kuhn(v);
    \end{code}
    Какой физический смысл происходящего?\\
    Оцените как-нибудь сверху и снизу асимптотику (в зависимости от $E, V, |M|$).\\
    Круто, если оценки сойдутся.\\
    Приведите тест (небольшой), на котором реализация работает некорректно.\\
    А можно ли ее завалить, если в начале сделать \t{random\_shuffle} всех ребер?

    \down
    {\bf Задача исследовательская.} Число баллов заранее не опеределено.

\end{MyList}
\end{document}
