\documentclass[12pt]{article}
\input{structure_analysis.tex}
\renewcommand{\bottomtitlespace}{3cm}

\begin{document}
	
\section{Анализ на задача \texttt{matrix}}
~\\
\indent\textit{Тагове: най-голям правоъгълник, запълнен с единици}
~

Ще разделим анализа на задачата на две части -- решаване на каноничната задача за най-голям правоъгълник, запълнен с единици, в масив и разглеждане на случаите за най-големия такъв правоъгълник в конкретната задача.

\subsection{Канонична задача}
Най-наивното решение на задачата е да си фиксираме два срещуположни върха на правоъгълника, който ще проверяваме за оптимален отговор и да видим, че наистина е запълнен с единици (ако все пак не искаме да е твърде бавно решението, това става с двумерни префиксни суми), като така постигаме $O((nm)^2)$ сложност. 

Идеята да си фиксираме част от правоъгълника е добра, но с два ъгъла (или пък с един) няма да се оправим. Визулано най-чисто ще ни се стори да фиксираме долния ръб на правоъгълника ($O(n)$ възможности) на всички редове. Така вместо да се притесняваме за всички фигури, образувани от единици във въведената таблица, от интерес са за нас само тези, които представляват стълбове от фиксирания ред нагоре. Така задачата се превръща в ``максимален подправоъгълник в хистограма'' (друга известна задача, която по някаква причина си има име). За да решим тази пък задача можем да забележим, че правоъгълникът ще взима някоя колона изцяло в себе си и можем да фиксираме нея ($O(m)$ опции) и да проверим наляво и надясно къде са най-близките колони, по-малки от фиксираната (става чрез \texttt{std::stack}). Сложността тук възлиза на $O(nm)$.

Допълнителни материали в интернет може да намерите като потърсите \textit{maximum rectangle of ones in a matrix; maximum rectangle in a histogram}.

\subsection{Тази задача}
С какво тази задача променя каноничната? Тук дефинираме по-голяма таблица на база въведената, която е периодична относно колоните и редовете. Именно тази периодичност ще ни позволи да изведем някакво решение за ``привидно'' голямата таблица. За лекота на израза ще казваме, че таблицата от условието $B$ се разделя на ``блокове'', всеки от които е идентичен с $A$.

Да допуснем, че правоъгълникът с най-голямо лице се разпростира през много блокове -- например $3$ блока (три е голямо число все пак) и това не е ограничено от размерите на $B$ (има още пространство, но просто то е пълно с нули да кажем). Това възможно ли е въобще? Не. Блоковете са идентични един на друг, голямата таблица $B$ е периодична -- каквото има в средния блок (през който нашия отговор-правоъгълник напълно минава), такова трябва да има и в първия и третия блок. Значи трябва да можем напълно да минаваме през тях също. А ние сме допуснали, че отговорът (максималния по площ правоъгълник) не минава. Противоречие.

Чрез това доказателство можем да се убедим, че съществуват следните случаи:
\begin{itemize}
	\item Отговор-правоъгълникът се разпростира в $4$ блокчета, долепени в $2$-на-$2$ конфигураия;
	\item Отговор-правоъгълникът се разпростира през всички колони на $B$, защото някои редове на $A$ са пълни с единици;
	\item Отговор-правоъгълникът се разпростира през всички редове на $B$, защото някои колони  на $A$ са пълни с единици;
	\item Всички елементи в $A$ са единици, съответно целият $B$ се явява отговор-правоъгълник.
\end{itemize}

Разглеждайки тях, ще намерим отговорът на задачата.

\begin{flushright}
	\textit{Автори: Иван Лупов, Атанас Димитров, Борис Михов}
\end{flushright}

\end{document}
