tag:blogger.com,1999:blog-91492603081627754422024-03-13T01:55:39.212+03:00Алгоритмы на С++ (олимпиадный подход)slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.comBlogger142125tag:blogger.com,1999:blog-9149260308162775442.post-10536489628773390582015-01-23T02:03:00.001+03:002015-01-23T03:38:55.141+03:00Олимпиада IT-CON 2014. Разбор + Материалы + Монитор<font face="Courier New"><a href="http://goo.gl/nqvfJk">Условия задач</a> <br /> <br /><strong><font color="#ff0000">A. Единицы</font></strong> <br />В этой задаче нужно было уметь находить количество единиц в строке и в числе <br /><a href="http://www.everfall.com/paste/id.php?aiy5an36oxbr">Решение</a> <br /> <br /><strong><font color="#ff0000">B. Коллекционер</font></strong> <br />Необходимо было найти количество уникальных элементов во входном массиве. <br />Задачу можно было решать как минимум двумя способами. <br />1. Воспользоваться контейнером, хранящим уникальные ключи. Например множеством <br />2. Отсортировать входной массив и найти количество пар, состоящих из соседних элементов, значения которых не равны. <br /><a href="http://www.everfall.com/paste/id.php?502p46g5kmdt">Решение</a> <br /> <br /><strong><font color="#ff0000">C. Декодирование по Хаффману <br /></font></strong>Задача решается жадно. Для хранения соответствия между буквенным и двоичным представлением можно было воспользоваться map’ом или хеш-таблицей, где в качестве ключа выступала бы двоичная интерпретация буквы алфавита. <br />Перебираем все символы исходного сообщения слева направо. Если в какой-то момент времени на текущим префиксе удалось набрать одно из двоичных представлений алфавита, то выводим эту букву в ответ. Отсекает текущий префикс и повторяем поиск очередной буквы. <br />Данный подход возможет благодарю свойству кода Хаффмана: никакой код буквы алфавита не является префиксом для другого кода этого же алфавита. <br /><a href="http://www.everfall.com/paste/id.php?n092x9hujtcy">Решение</a> <br /> <br /><strong><font color="#ff0000">D. Восстановление перестановки <br /></font></strong>От участников требовалось реализовать квадратичное решение. <br />Авторское решение разматывала клубок, начиная с максимального элемента перестановки. <br />Можно заметить, что максимальный элемент перестановки будет соответствовать самому правому нулю в таблице инверсий. После нахождения такого элемента его можно “вырезать” и уменьшить все элементы из таблицы инверсий, находящихся правее этого элемента. Далее нужно повторить поиск максимального элемента в модифицированной перестановки(без учета вырезанного элемента) и так до тех пор, пока не найдутся все элементы перестановки <br /><a href="http://www.everfall.com/paste/id.php?847fa6oe4hvj">Решение</a> <br /> <br /><strong><font color="#ff0000">E. Калькулятор</font></strong> <br />Очень красивая и несложная задача на динамическое программирование. <br />Заведем массив на n элементов(N <= 1000000) <br />Для каждого i <= n найдем ответ на данную задачу. <br />Начнем с базы динамики. Для i = 1, очевидно, что ответ будет 0. Далее переберем все элементы в интервале [2,n]. В текущий элементы i мы могли попасть из трех состояний: i-1, i/2, i/3. Необходимо выбрать предыдущее состоянии, которое может быть набрано за минимальное количество действий. Также необходимо учесть, что состояния i/2 и i/3 можно рассматривать только в том случае, если i делится на 2 и на 3 без остатка. <br /><a href="http://www.everfall.com/paste/id.php?7ecw4zg3yi0o">Решение</a> <br /> <br /><strong><font color="#ff0000">F. Генерация Z-матрицы</font></strong> <br />Решение задание подразумевало рекурсивную реализацию заполнения матрицы. Реализацию рекурсивных переходов и расчет границ блоков смотрите в авторском решении. В данном решении матрица 2*2 заполняется в двойном цикле, но можно было оставить рекурсивный переход до матрицы 1*1. <br /><a href="http://www.everfall.com/paste/id.php?hznsa3nuf8og">Решение</a> <br /> <br /><strong><font color="#ff0000">G. Буквы по кругу</font></strong> <br />Задачу нужно было свести к поиску подстроки в строке <br /><a href="http://www.everfall.com/paste/id.php?hl1k0is0vk3u">Решение</a> <br /> <br /><strong><font color="#ff0000">H. Объезд королевства <br /></font></strong>Классическая задача на перебор с возвратом. Ограничения были подобраны так, чтобы задача укладывалась в time limit. <br /><a href="http://www.everfall.com/paste/id.php?kl8epbw0ohnn">Решение</a> <br /> <br /><strong><font color="#ff0000">I. Следующий палиндром</font></strong> <br />Задача на аккуратность реализации и на учет всех случаев. Особое внимание стоит уделить центральному элементу палиндрома в случае нечетной длины, а также увеличению размера палиндрома(например при входном палиндроме 99 ответ будет 101) <br /><a href="http://www.everfall.com/paste/id.php?6twxi58w483z">Решение</a> <br /> <br /><strong><font color="#ff0000">J. Карточная пирамида</font></strong> <br />Задачу можно было решать с помощью формулы, зная формулу арифметической прогрессии <br /><a href="http://www.everfall.com/paste/id.php?2wceo3he7geq">Решение</a> <br /> <br />Условия задач: <a title="http://goo.gl/nqvfJk" href="http://goo.gl/nqvfJk">http://goo.gl/nqvfJk</a> <br />Полный монитор: <a title="http://goo.gl/wkbAOu" href="http://goo.gl/wkbAOu">http://goo.gl/wkbAOu</a> <br />Тесты: <a title="http://goo.gl/QwmEee" href="http://goo.gl/QwmEee">http://goo.gl/QwmEee</a> <br /> <br /><strong>Победители: <br /></strong><img src="https://lh6.googleusercontent.com/-DuOYjlDIeZU/VMGXTeE-6II/AAAAAAAACOc/t_BHHAq28vc/w765-h510-no/1.jpg" /> <br />Победители IT-CON 2014 <br /></font> <p><img src="https://lh6.googleusercontent.com/-IC5EnJ-aIBo/VMGXTVtimkI/AAAAAAAACOY/bP3iSu4l4_4/w765-h510-no/3.jpg" /> <br /><font face="Courier New">Лучший участник олимпиады от компании Mirafox (Евгений) – 2 место в общем зачете</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com4tag:blogger.com,1999:blog-9149260308162775442.post-8178388906430179792013-11-22T07:59:00.001+04:002013-11-22T07:59:12.639+04:00Олимпиада IT-CON 2013. Разбор + Материалы + Монитор<p align="justify"><a href="https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxzbGlwc3RhazJ8Z3g6NGQzOTYzNzliY2RlMDdmNA"><strong><font face="Courier New">Условия задач</font></strong></a> <br /> <br /><font face="Courier New"><strong><font color="#ff0000">A. Счастливые билеты</font> <br /></strong>Суть задачи сводится к грамотному написанию двух функций: <br />   1. Проверка счастливости по-московски <br />   2. Проверка счастливости по-питерски. <br />Задача имела поощрительный характер. <br /></font><a href="http://www.everfall.com/paste/id.php?zl5zd1de48w2"><strong><font face="Courier New">Решение</font></strong></a> <br /><font face="Courier New">   <br /></font><font face="Courier New"><strong><font color="#ff0000">B. Пагинация</font> <br /></strong>Задача решается очень просто, если нумерации участников и листов вести с нуля. А именно: <br />n / k – номер листа <br />n % k – номер строки на нужном листе. <br />Для перехода на нумерацию с единицы можно было воспользоваться таким приемом: <br />(n - 1) / k + 1 – номер листа <br />(n - 1) % k + 1 – номер строки. <br /></font><a href="http://www.everfall.com/paste/id.php?r4od0lm9327i"><strong><font face="Courier New">Решение</font></strong></a> <br /> <br /><font face="Courier New"><strong><font color="#ff0000">C. Палиндромы</font> <br /></strong>Еще одна поощрительная задача. Суть ее сводится к написанию функции проверки строки на палиндромность: <br /></font></p> <pre class="cpp" style="font-family: monospace"><ol><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"><span style="color: #0000ff">bool</span> is_palindrome<span style="color: #008000">(</span><span style="color: #0000ff">const</span> string <span style="color: #000040">&</span>s<span style="color: #008000">)</span><span style="color: #008000">{</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">int</span> l <span style="color: #000080">=</span> <span style="color: #0000dd">0</span>, r <span style="color: #000080">=</span> s.<span style="color: #007788">size</span><span style="color: #008000">(</span><span style="color: #008000">)</span> <span style="color: #000040">-</span> <span style="color: #0000dd">1</span><span style="color: #008080">;</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">while</span> <span style="color: #008000">(</span>l <span style="color: #000080"><</span> r<span style="color: #008000">)</span> <span style="color: #008000">{</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">if</span> <span style="color: #008000">(</span>s<span style="color: #008000">[</span>l<span style="color: #000040">++</span><span style="color: #008000">]</span> <span style="color: #000040">!</span><span style="color: #000080">=</span> s<span style="color: #008000">[</span>r<span style="color: #000040">--</span><span style="color: #008000">]</span><span style="color: #008000">)</span></div><li style="vertical-align: top; font-weight: bold"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">return</span> <span style="color: #0000ff">false</span><span style="color: #008080">;</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #008000">}</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">return</span> <span style="color: #0000ff">true</span><span style="color: #008080">;</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"><span style="color: #008000">}</span></div></li></ol></pre>
<p align="justify"><a href="http://www.everfall.com/paste/id.php?7cw6zyhtk8vy"><strong><font face="Courier New">Решение</font></strong></a>
<br />
<br /><font face="Courier New"><strong><font color="#ff0000">D. Арифметическая прогрессия</font>
<br /></strong>Пожалуй самая сложна задача =).
<br /></font><a href="http://www.everfall.com/paste/id.php?xyyf0kq5zim0"><strong><font face="Courier New">Решение</font></strong></a>
<br />
<br /><font face="Courier New"><strong><font color="#ff0000">E. Права пользователя</font>
<br /></strong>В задаче предполагалось использовать битовые операции и умение использовать структуру данных “словарь”. Ключевой момент – умение установить i-ый бит число в 1 или в 0. Более подробно о распространненных битовых операциях можно почитать <a href="http://cppalgo.blogspot.ru/2010/10/blog-post.html"><u>здесь</u></a>.
<br /><a href="http://www.everfall.com/paste/id.php?uy7vxbu4oq0n"><strong>Решение</strong></a>
<br />  <br /><strong><font color="#ff0000">F. Шифр Кардано</font>
<br /></strong>Смысл задачи сводится к умению поворачивать квадратную матрицу по часовой стрелке.
<br /></font></p>
<pre class="cpp" style="font-family: monospace"><ol><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"><span style="color: #0000ff">void</span> transposition<span style="color: #008000">(</span><span style="color: #0000ff">int</span> mask<span style="color: #008000">[</span><span style="color: #008000">]</span><span style="color: #008000">[</span>SIZE<span style="color: #008000">]</span><span style="color: #008000">)</span><span style="color: #008000">{</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">int</span> tmp<span style="color: #008000">[</span>SIZE<span style="color: #008000">]</span><span style="color: #008000">[</span>SIZE<span style="color: #008000">]</span><span style="color: #008080">;</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">for</span> <span style="color: #008000">(</span><span style="color: #0000ff">int</span> i<span style="color: #000080">=</span><span style="color: #0000dd">0</span><span style="color: #008080">;</span>i<span style="color: #000080"><</span>n<span style="color: #008080">;</span><span style="color: #000040">++</span>i<span style="color: #008000">)</span><span style="color: #008000">{</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000ff">for</span> <span style="color: #008000">(</span><span style="color: #0000ff">int</span> j<span style="color: #000080">=</span><span style="color: #0000dd">0</span><span style="color: #008080">;</span>j<span style="color: #000080"><</span>n<span style="color: #008080">;</span><span style="color: #000040">++</span>j<span style="color: #008000">)</span><span style="color: #008000">{</span></div><li style="vertical-align: top; font-weight: bold"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> tmp<span style="color: #008000">[</span>i<span style="color: #008000">]</span><span style="color: #008000">[</span>j<span style="color: #008000">]</span> <span style="color: #000080">=</span> mask<span style="color: #008000">[</span>n<span style="color: #000040">-</span>j<span style="color: #000040">-</span><span style="color: #0000dd">1</span><span style="color: #008000">]</span><span style="color: #008000">[</span>i<span style="color: #008000">]</span><span style="color: #008080">;</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> </div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #008000">}</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #008000">}</span></div><li style="vertical-align: top; font-weight: normal"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"> <span style="color: #0000dd">memcpy</span><span style="color: #008000">(</span>mask,tmp,<span style="color: #0000dd">sizeof</span><span style="color: #008000">(</span>tmp<span style="color: #008000">)</span><span style="color: #008000">)</span><span style="color: #008080">;</span></div><li style="vertical-align: top; font-weight: bold"><div style="vertical-align: top; background: none transparent scroll repeat 0% 0%; padding-bottom: 0px; padding-top: 0px; font: 1em/1.2em monospace; padding-left: 0px; margin: 0px; padding-right: 0px"><span style="color: #008000">}</span></div></li></ol></pre>
<p align="justify"><a href="http://www.everfall.com/paste/id.php?k3omqzcuakfc"><strong><font face="Courier New">Решение</font></strong></a>
<br />
<br /><strong><font color="#ff0000">G. Количество секретных баз</font>
<br /></strong><font face="Courier New">Данную задачу можно было решать по-разному. Рассмотрим два решения.
<br /></font><font face="Courier New"><em>1. Рекурсивная закраска связных областей
<br /></em>   По сути дела в условии задачи нет информации о том, что кроме военных баз на карте могут находиться другие объекты. Также сказано, что военные базы не пересекаются и не соприкасаются. Поэтому можно смело свести задачу к поиску количества компонент связностей, реализуя обычный DFS(поиск в глубина)
<br /></font><font face="Courier New"><em>2. Поиск самой северной точки военной базы.
<br /></em>   Рассмотрим военную базу размером 2:
<br /></font></p>
<p align="justify"><a href="http://lh3.ggpht.com/-IRUfKZuW2lE/Uo7WiiZC9EI/AAAAAAAACKk/Sj2au6Zam0Q/s1600-h/BtyzkgMfQQ1b3aXeunP8dgHfkzgEIksIH6Kj%25255B1%25255D.png"><img title="BtyzkgMfQQ1b3aXeunP8dgHfkzgEIksIH6KjlNYNTPs=w217-h207-p-no[1]" style="border-left-width: 0px; border-right-width: 0px; border-bottom-width: 0px; float: none; margin-left: auto; display: block; border-top-width: 0px; margin-right: auto" border="0" alt="BtyzkgMfQQ1b3aXeunP8dgHfkzgEIksIH6KjlNYNTPs=w217-h207-p-no[1]" src="http://lh5.ggpht.com/-A1Df8OqbV-M/Uo7WjBfm2WI/AAAAAAAACKs/-iG3vP1JJt8/BtyzkgMfQQ1b3aXeunP8dgHfkzgEIksIH6Kj.png?imgmax=800" width="217" height="207" /></a><font face="Courier New">Для того,чтобы проверить является ли текущая точка самой северной точкой базы нужно посмотреть на три соседние клетки: вверх, вправо и влево. Если все три клетки не заняты военной базой, значит текущая точка является самой северной.
<br /></font><a href="http://www.everfall.com/paste/id.php?g7uj3owu2uip"><font face="Courier New"><strong>Решение DFS</strong></font></a><font face="Courier New"><strong>
<br /></strong></font><a href="http://www.everfall.com/paste/id.php?fkzkh5yzd3bb"><font face="Courier New"><strong>Решение (Поиска самой северной точки)</strong></font></a> </p>
<p><font face="Courier New"><font color="#ff0000"><strong>H. T9</strong></font><strong>
<br /></strong>Еще одна несложная задача. На первом этапе переводим строковое представление контакта в цифровой ряд, который нужно набрать. При этом нужно обратить внимание на:
<br />1) Возможное наличие пробелов в начале и в конце строкового представления контакта. На этом моменте падали почти все решения.  <br />2) Нужно хранить изначальный вариант контакта для его последующего вывода
<br />3) Корректно обрабатывать буквы в разных регистрах.
<br /><a href="http://www.everfall.com/paste/id.php?5ehw9loqzlzz"><strong>Решение</strong></a>
<br /></font><font face="Courier New">
<br /></font><font face="Courier New"><strong><font color="#ff0000">I. Пятнашки 3x3</font>
<br /></strong>В самом худшем случае любые пятнашки размером 3x3 можно собрать не более за 31 шаг. Данную задачу по замыслу жюри нужно было решать BFS’ом, но в последний момент было принято решение ослабить максимальное количество шагов до 15. В результате получилось, что грамотно написанный DFS без меморизации заходил в установленные лимиты.
<br />В написании BFS’а есть интересный момент:
<br />Как организовать быструю проверку – было ли данное состояние пройдено на предыдущих шагах. Тут можно воспользоваться двумя подходами:
<br />  1) <strong>Ленивый</strong>. Представим поле в виде 9-ти значного числа, которое состоит из цифр поля, записанных слева направо, сверх вниз. Пустое поле будем кодировать нулем. При этом получается, что самое большое число, которое может быть 876543210, которое с успехом помещается в int. Общее количество всех валидных состояний в пятнашках равно 9! / 2 = 181440. Поэтому для хранения все предыдущих состояний можно использовать множество, в котором хранить закодированное состояние пятнашки. Используя множество можно с логарифмической сложностью ответить на вопрос – было ли данное состояние пройдено на предыщущих шагах
<br />   2) <strong>Комбинаторный</strong>. Используем всю ту же логику что в первом пункте, но обращаем внимание на то, что общее количество всех перестановок сравнительно невелико. Если каждое закодированное состояние пятнашки представимо в виде перестановки, то состояние пятнашки можно кодировать не самой перестановкой, а ее порядковым номером в лексикографическом порядке. Получается что что можно множество заменить на битовый массив размером 9!. Сложность поиска текущего состояние среди предыдущих уменьшается до O(1).
<br />
<br />BFS можно заменить на алгоритм A*. В качестве оценочной функции можно использовать сумму манхэттенских расстояний для каждой цифры. Начальная позиция цифры совпадает с ее позицией в текущем состоянии. Конечная позиция – позиция цифры в финальном состоянии. Чем меньше оценочная функция тем ближе данное состояние к финишу.
<br /><a href="http://www.everfall.com/paste/id.php?7scsxelgts86"><strong>Решение</strong></a>
<br />
<br /><font color="#ff0000"><strong>Арифметическое выражение</strong></font>
<br />Последняя задачу на динамику. Будем последовательно будем находить ответ на задачу для каждого числа от 0 до n.
<br />Пусть len(j) – длина арифметического выражения для числа j. Если число j нельзя набрать, то длина равна 0.
<br />
<br />Текущее число i можно набрать тремя способами:
<br />1) Непосредственно разрешенным набором цифр. Если можно набрать число данным способом, то второй и третий способ можно не проверять.
<br />2) i = A + (i-A), где A принадлежит интервалу [1, i-1]. Для каждого числа из этого интервала уже найден ответ. Получается, что len(i) = len(A) + 1 + len(i-A). Заметим, что размер интервала можно сократить в два раза.
<br />Для каждого числа нужно хранить метку: получено ли данное число с помощью плюса двух арифметических выражений.
<br />3) i = P * (i/P), где P принадлежит интервалу [2, sqrt(i)]. При этом i делится на P без остатка. len(i) = len(P) + 1 + len(i/P). Если число P было получено оптимальным способом с использованием сложения, то его арифметическое выражение при формировании числа i нужно обрамить в скобки и добавить к len(i) число 2. Аналогично нужно поступить и с числом i/P.
<br />
<br />Последовательно перебирая все способы получения числа i указанными тремя способами находим минимальную длину арифметического выражения, которым можно получить данное число i, сохраняем полученное арифметическое выражения для дальнейшего подсчета других числе больше i
<br /><a href="http://www.everfall.com/paste/id.php?tsnwa35m6f2b"><strong>Решение</strong></a>
<br />
<br />Условия задач: <a title="http://goo.gl/ApbiPW" href="http://goo.gl/ApbiPW">http://goo.gl/ApbiPW</a>
<br />Полный монитор: <a title="http://goo.gl/lAAkdh" href="http://goo.gl/lAAkdh">http://goo.gl/lAAkdh</a>
<br />Тесты: <a title="http://goo.gl/5anx35" href="http://goo.gl/5anx35">http://goo.gl/5anx35</a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com3tag:blogger.com,1999:blog-9149260308162775442.post-7227023305004177602012-10-25T16:22:00.001+04:002012-10-25T16:23:26.882+04:00IT-CON 2012(Фотоотчет)<p align="center"><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh4.googleusercontent.com/-VPNMlZAeTIc/UIkpY4qHWUI/AAAAAAAAB8I/dhtN-0QQNDQ/s747/1.jpg" /> <br /><font face="Courier New">Начало разбора <br /></font></p> <a name='more'></a> <p align="center"><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; display: block; float: none; margin-left: auto; border-top: 0px; margin-right: auto; border-right: 0px; padding-top: 0px" border="0" src="https://lh6.googleusercontent.com/-xSSGbArydXA/UIkpbLpeeCI/AAAAAAAAB8c/BNmw9Dyj6p0/s747/2.jpg" /><font face="Courier New">Сказ о том, как можно привести букву к нижнему регистру =) <br /></font> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-Z41WtfAVhTg/UIkpbChfRzI/AAAAAAAAB8g/-CZb3WHrmdA/s747/3.jpg" /> <br /><font face="Courier New">Денчик демонстрирует свой прикус <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-i6yAdkKIKVE/UIkpcXqoDlI/AAAAAAAAB8s/86_2JtZxjpM/s747/4.jpg" /> <br />Денчик сдерживает эмоции <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-_V0oX6SDNsI/UIkpcXKklmI/AAAAAAAAB80/ASw7XcmTV-g/s747/5.jpg" /> <br />Дмитрий скромен и кроток <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh3.googleusercontent.com/-IqXFhbisSbs/UIkpc3fQkMI/AAAAAAAAB84/1eu3M1WjHmY/s747/6.jpg" /> <br />Паша забирает добычу <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh4.googleusercontent.com/-Z5Yoz862wU4/UIkpdiu6B6I/AAAAAAAAB9A/vg-oxyfV_Lk/s747/7.jpg" /> <br />Валерий Викторович показывает свое отношение к происходящему <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-5H1Zy2Irpiw/UIkpesl_tGI/AAAAAAAAB9I/M1ZlwFdvASk/s747/8.jpg" /> <br />Андрей демонстрирует свой ушной пирсинг <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh4.googleusercontent.com/-VlNUqxx_XeQ/UIkpelhQ_jI/AAAAAAAAB9M/ARxD_6fHMZE/s747/9.jpg" /> <br />Голливудская улыбка <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-oU4CmbnMWTg/UIkpZANhwqI/AAAAAAAAB8M/_j3Rq1oA_sI/s747/10.jpg" /> <br />Виталик не сдерживает радости <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh4.googleusercontent.com/-d3IgSqTIqqo/UIkpZU8rYhI/AAAAAAAAB8Q/PF3duaaWkog/s747/11.jpg" /> <br />Завершение награждения <br /> <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh6.googleusercontent.com/-OM25LyCwh8s/UIkpanHQjyI/AAAAAAAAB8Y/3UfzOGLX7iI/s747/12.jpg" /> <br />Победила дружба</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com1tag:blogger.com,1999:blog-9149260308162775442.post-46123280946829037862012-10-24T20:55:00.001+04:002012-10-25T16:42:07.531+04:00IT-CON 2012 (Олимпиада для студентов 3-5 курсов) Разбор + Материалы + Монитор<p align="justify"><font face="Courier New"><a href="https://sites.google.com/site/slipstak2/%D0%A3%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F%20%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%20%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%BE%20%D1%82%D1%83%D1%80%D0%B0%28%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%BE%D0%B9%20%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82%29.docx?attredirects=0&d=1"><strong>Условия задач</strong></a> <br /> <br /><strong>Разбор: <br /></strong><font color="#ff0000"><strong><font size="3">A. Трехзначные числа</font> <br /></strong></font><font color="#333333">Задачу можно решать перебором всех чисел в интервале [100,999], что дает генерацию чисел в порядке возрастания. Для каждого числа находим сумму цифр и сравниваем ее с заданной. Удовлетворяющие числа будем хранить в динамическом массиве. <br /></font> <br /><a href="http://www.everfall.com/paste/id.php?g4pjkuhjnzka">Решение 1(конвертация числа в строку)</a> <br /><a href="http://www.everfall.com/paste/id.php?l6ip4m91l5hp">Решение 2(откусывание последней цифры числа)</a> <br /><a href="http://www.everfall.com/paste/id.php?oysodkby1pbq">Решение 3(перебор цифр)</a> <br /> <br /><font color="#ff0000"><strong><font size="3">B. Электронная почта <br /></font></strong><font color="#000000">Задача ну умение переводить буквы латинского алфавита в нижний регистр. Пожалуй самая легкая задача олимпиады. <br /> <br /><a href="http://www.everfall.com/paste/id.php?4zzgcdopilc3">Решение 1(с использованием функции tolower())</a> <br /><a href="http://www.everfall.com/paste/id.php?wzzitbjy5ho1">Решение 2(сопоставление заглавных и прописных букв)</a> <br /><a href="http://www.everfall.com/paste/id.php?05zbzr8fvxzf">Решение 3(с использованием смещения)</a></font> <br /></font> <br /><font color="#ff0000" size="3"><strong>C. Римские числа <br /></strong></font><font color="#333333">Решение задачи описано в самом условии. На каждом шаге рассмотрим текущую цифру и последующую. Если текущая цифра меньше последующей, то к результирующему ответу прибавляем разницу последующей цифры и текущей и пропускаем эти две римские цифры. Если сложилась ситуация, что текущая цифра не меньше последующей, то к ответу прибавляется только значение текущей цифры и переходим к последующей цифре. Если на каком то этапе можно рассмотреть только текущую цифру, то прибавляем ее</font> значение к ответу. <br /> <br /><a href="http://www.everfall.com/paste/id.php?wo63kcb7itwl">Решение</a> <br /> <br /><strong><font color="#ff0000" size="3">D. Уникальные элементы <br /></font></strong>Самым простым решением было “загнать” все элементы в set и вывести количество элементов получившегося set’a. <br />В рамках другого решения можно было отсортировать массив любым известным алгоритмом сортировки, алгоритмическая сложность которого не превышала бы квадратичную. В результате можно было перебрать все пары соседних элементов и найти те из них, где текущий элемент не равен последующему. Количество таких пар + 1 является ответом на задачу. <br /> <br /><a href="http://www.everfall.com/paste/id.php?dw8m0rqyuj2a">Решение 1 (с использованием set’a)</a> <br /><a href="http://www.everfall.com/paste/id.php?0bwhhxo7whv0">Решение 2 (с использованием sort’a)</a> <br />  <br /><strong><font color="#ff0000" size="3">E. Сапер <br /></font></strong>Чисто техническая задача. Жизнь существенно упростит массив движений, в котором нужно записать смещения в 8 направлений:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>... </li> <li><font color="#0000ff">int</font> moveX[8] = {-1,-1,-1, 0, 0, 1,1,1}; </li> <li><font color="#0000ff">int</font> moveY[8] = {-1, 0, 1,-1, 1,-1,0,1}; </li> <li><font color="#0000ff">bool</font> correct(<font color="#0000ff">int</font> x, <font color="#0000ff">int</font> y) { </li> <li>  <font color="#0000ff">if</font> (x < 1 || y < 1) <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>  <font color="#0000ff">if</font> (x > n || y > m) <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>  <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>} </li> <li>... </li> <li><font color="#0000ff">for</font> (<font color="#0000ff">int</font> p=0;p<8;++p){ </li> <li>  <font color="#0000ff">int</font> x = i + moveX[p]; </li> <li>  <font color="#0000ff">int</font> y = j + moveY[p]; </li> <li>  <font color="#0000ff">if</font> (correct(x,y) && mas[x][y] !=-1) </li> <li>    ++mas[x][y]; </li> <li>... </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p align="justify"><font face="Courier New"><a href="http://www.everfall.com/paste/id.php?rgzffkqcjpvd">Решение</a> <br /> <br /><strong><font color="#ff0000" size="3">F. Генерация подмножеств <br /></font></strong>Классическая задача по комбинаторике. <br />Рассмотрим первое решение. Пусть N = 3. Рассмотрим все числа от 0 до 2^n – 1. <br />           123 <br />      0 –> 000 = {} <br />      1 –> 001 = {3} <br />      2 –> 010 = {2} <br />      3 –> 011 = {2,3} <br />      4 –> 100 = {1} <br />      5 –> 101 = {1,3} <br />      6 –> 110 = {1,2} <br />      7 –> 111 = {1,2,3} <br /> <br /><a href="http://www.everfall.com/paste/id.php?ly7hftpjyjxc">Решение 1 (через двоичное представление)</a> <br /><a href="http://www.everfall.com/paste/id.php?2eb6vz6555g4">Решение 2 (рекурсивное с построением дерева состояний)</a> <br /> <br /><strong><font color="#ff0000" size="3">G. Количество нулей у факториала <br /></font></strong>Стоит заметить, что количество нулей, на которые заканчивается факториал равно количеству десяток в разложении этого факториала на множители. Десятка состоит из двух простых сомножителей. При этом множитель 5 в разложении факториала на простые множители будет встречаться намного реже, чем множитель 2. Поэтому количество нулей у факториала на конце будет равно количеству пятерок в разложении его на простые множители. <br /> <br /><a href="http://www.everfall.com/paste/id.php?c53qc9ry8xfn">Решение 1</a> <br /><a href="http://www.everfall.com/paste/id.php?wnjrli8dz8tf">Решение 2</a> <br /> <br /><strong><font color="#ff0000" size="3">H. Язык разметки RHTML 1.0. <br /></font></strong>Можно применить один из двух подходов: конечный автомат и механизм “откусывания”. <br />Первый пишется дольше, но работает всегда быстрее и легко масштабируется. Второй способ пишется проще и работает чуть медленнее. Главное аккуратность и обильное тестирование. <br /> <br /><a href="http://www.everfall.com/paste/id.php?4i6m4ho16u3q">Решение 1 (конечный автомат)</a> <br /><a href="http://www.everfall.com/paste/id.php?zhw8kfgmqglz">Решение 2 (с помощью “откусывания”)</a> <br /><a href="http://www.everfall.com/paste/id.php?7biny2ns3atv">Решение 3 (конечный автомат + С-строка) [Автор: Сагунов Данил]</a> <br /> <br /><strong><font color="#ff0000" size="3">I. Объединение прямоугольников <br /></font></strong>Единственная задача, для которой я не писал тесты, а взял оригинальные с задачника Федора Меньшикова. <br />Я ее уже рассматривал <a href="http://cppalgo.blogspot.com/2010/11/6.html">ранее</a>(6D. Площадь прямоугольников) <br /> <br /><a href="http://www.everfall.com/paste/id.php?q67po53h6nwp">Решение</a> <br /> <br /><strong><font color="#ff0000" size="3">J. Путь в матрице <br /></font></strong></font><font face="Courier New">Оригинальное условие задачи находится здесь: </font><a href="http://projecteuler.net/problem=83"><font face="Courier New">http://projecteuler.net/problem=83</font></a> <br /><font face="Courier New">Я предполагал решение задачи через алгоритм Дейкстры, но ограничения были подобраны так, что и реализация алгоритма Флойда также укладывались в отведенные лимиты. При таком подходе представляет исходную матрицу в виде графа, где каждая вершина имеет до 4 соседей. Ребро между (i,j) и (i+1,j) вершиной будет иметь вес a[i][j], где a – исходная матрица. После того как граф построен можно запускать вышеописанные алгоритмы. <br />Участники, сдавшие решения предложили обычный BFS на матрице. Это решение пишется намного проще. <br /> <br /><a href="http://www.everfall.com/paste/id.php?m47wc54o07fm">Решение 1(алгоритм Флойда)</a> <br /><a href="http://www.everfall.com/paste/id.php?e7lm520u7gjv">Решение 2(алгоритм Дейкстры)</a> <br /><a href="http://www.everfall.com/paste/id.php?kmdp00ewdktp">Решение 3(BFS)</a> <br /> <br /> <br />Тесты и условия задач: <a title="http://goo.gl/DvISB" href="http://goo.gl/DvISB">http://goo.gl/DvISB</a> <br />Авторские решения:     <a title="http://goo.gl/lyEjn" href="http://goo.gl/lyEjn">http://goo.gl/lyEjn</a> <br />Размороженный монитор: <a href="http://goo.gl/QOTRa">http://goo.gl/QOTRa</a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com4tag:blogger.com,1999:blog-9149260308162775442.post-5968147859913208652012-08-28T20:28:00.001+04:002012-08-28T20:28:09.621+04:00Нахождение количества компонент связности<p><font face="Courier New">Рассмотрим базовую задачу. <br /><strong><u>Условие:</u></strong> <br />Дан неориентированный граф G, имеющий N вершин и M ребер. Чтобы все рассмотренные подходы имели практических смысл, ограничим N<=1000. <br />Необходимо найти количество компонент связности данного графа. <br /> <br /><u><strong>Формат входных данных</strong>:</u> В первой строке входного файла находятся N и M, разделенные пробелом. Далее идет M строк, содержащих пару вершин, между которыми находится ребро. Вершины нумеруются с 1. <br /><strong><u>Формат выходных данный:</u></strong> В единственной строке выдать количество компонент связности графа. <br /> <br />Пример: <img border="0" align="right" src="https://lh3.googleusercontent.com/-6CQfoj14dJE/UDzkvFDy5DI/AAAAAAAAB70/NQx5lF7U1eY/s453/connected_components.png" /> <br /><strong>input.txt</strong> <br />15 11 <br />1 2 <br />2 3 <br />2 11 <br />10 11 <br />11 12 <br />11 15 <br />4 12 <br />12 13 <br />8 14 <br />7 14 <br />5 6 <br /><strong>output.txt <br /></strong>4 <br /></font></p> <font face="Courier New"> <p> <br /> <br /> <br />Компонента связности неориентированного графа является подграф, в котором для любой пары вершин v и u существует путь. Между двумя различными компонентами связности не существует пути. <br /> <br />Задача стара, как мир. Но тем не менее сегодня покажу несколько подходов по ее решению. <br /> <br /><strong><font color="#0000ff" size="3">1. Поиск в глубину(DFS) <br /></font></strong>Самое классическое решение. Даже комментировать особо нечего.</p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">const</font> <font color="#0000ff">int</font> SIZE = 1e3 + 10; </li> <li>vector<<font color="#0000ff">int</font>> adj[SIZE]; </li> <li><font color="#0000ff">bool</font> usd[SIZE]; </li> <li>... </li> <li><font color="#0000ff">void</font> dfs(<font color="#0000ff">int</font> cur) { </li> <li>  usd[cur] = <font color="#0000ff">true</font>; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<adj[cur].size();++i) { </li> <li>    <font color="#0000ff">int</font> nxt = adj[cur][i]; </li> <li>    <font color="#0000ff">if</font> (!usd[nxt]) </li> <li>      dfs(nxt); </li> <li>  } </li> <li>} </li> <li><font color="#0000ff">int</font> connected_components_amount_dfs() { </li> <li>  <font color="#0000ff">int</font> cnt = 0; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1; i<=n; ++i) { </li> <li>    <font color="#0000ff">if</font> (!usd[i]) { </li> <li>      dfs(i); </li> <li>      ++cnt; </li> <li>    } </li> <li>  } </li> <li>  <font color="#0000ff">return</font> cnt; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p>Граф храним в виде списка смежности(строка 2). Общая сложность решения $latex O(N + M)$. <br /><a href="http://www.everfall.com/paste/id.php?r4ehf6hk7zau">Решение</a></p> <p align="justify"><strong><font color="#0000ff" size="3">2. DSU подобная структура(ленивый подход) <br /></font></strong>Будем делать конденсацию компоненты в одну вершину. Идея следующая: будем последовательно обрабатывать ребра. Каждая компонента связности будет представлена одной своей вершиной(титульная). При этом неважно какой. По ходу обработки ребер титульная вершина компонент может меняться. <br />В итоге для нахождения количества компонент связности нужно найти количество титульных вершин. <br /></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">const</font> <font color="#0000ff">int</font> SIZE = 1e3 + 10; </li> <li><font color="#0000ff">int</font> p[SIZE]; </li> <li><font color="#0000ff">bool</font> usd[SIZE]; </li> <li>... </li> <li><font color="#0000ff">int</font> connected_components_amount_dsu() { </li> <li>  </li> <li>  scanf(<font color="#a31515">"%d %d"</font>, &n, &m); </li> <li>  </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) { </li> <li>    p[i] = i; </li> <li>  } </li> <li>  </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<m;++i) { </li> <li>    scanf(<font color="#a31515">"%d %d"</font>, &f, &s); </li> <li>    <font color="#0000ff">int</font> par = p[f]; </li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> j=1;j<=n;++j) { </li> <li>      <font color="#0000ff">if</font> (p[j] == par) </li> <li>        p[j] = p[s]; </li> <li>    } </li> <li>  } </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) </li> <li>    usd[p[i]] = <font color="#0000ff">true</font>; </li> <li>  <font color="#0000ff">int</font> cnt = 0; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) { </li> <li>    <font color="#0000ff">if</font> (usd[i]) ++cnt; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> cnt; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p>Заметим, что сам граф непосредственно вообще никак не хранится. Общая сложность $latex O(M*N)$  <br /><a href="http://www.everfall.com/paste/id.php?er98s0r6xzw6">Решение</a></p> <p align="justify"><strong><font color="#0000ff" size="3">3. Система непересекающихся множеств (DSU)</font></strong> <br />Реализацию, представленную выше можно существенно усовершенствовать. При добавлении нового ребра будем “мерджить меньшее подмножество к большему” + сжимать пути. У <a href="http://e-maxx.ru/algo/dsu#7">emaxx’а</a> рассматривается доказательство того, что ассимптотика обработки одного ребра равна $latex O(\alpha (N))$, где $latex \alpha (N)$ – обратная функция Аккермана. <br /></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">const</font> <font color="#0000ff">int</font> SIZE = 1e3 + 10; </li> <li>  </li> <li><font color="#0000ff">int</font> p[SIZE]; </li> <li><font color="#0000ff">int</font> size[SIZE]; </li> <li>  </li> <li><font color="#0000ff">int</font> par(<font color="#0000ff">int</font> x) { </li> <li>  <font color="#0000ff">return</font> p[x] == x ? x : p[x] = par(p[x]); </li> <li>} </li> <li><font color="#0000ff">int</font> connected_components_amount_dsu() { </li> <li>  </li> <li>  scanf(<font color="#a31515">"%d %d"</font>, &n, &m); </li> <li>  </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) { </li> <li>    p[i] = i; </li> <li>    size[i] = 1; </li> <li>  } </li> <li>  </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<m;++i) { </li> <li>    scanf(<font color="#a31515">"%d %d"</font>, &f, &s); </li> <li>    f = par(f); s = par(s); </li> <li>    <font color="#0000ff">if</font> (f != s) { </li> <li>      <font color="#0000ff">if</font> (size[f] > size[s]) </li> <li>        swap(f,s); </li> <li>      p[f] = s; </li> <li>      size[s] += size[f]; </li> <li>    } </li> <li>  } </li> <li>  <font color="#0000ff">bool</font> usd[SIZE]; </li> <li>  memset(usd, 0, <font color="#0000ff">sizeof</font>(usd)); </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) </li> <li>    usd[par(i)] = <font color="#0000ff">true</font>; </li> <li>  <font color="#0000ff">int</font> cnt = 0; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) { </li> <li>    <font color="#0000ff">if</font> (usd[i]) ++cnt; </li> <li>  } </li> <li>  </li> <li>  <font color="#0000ff">return</font> cnt; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> </font> <p align="justify"><font face="Courier New">Как и прежде сам граф не хранится в виде матрицы смежности. Общая сложность $latex O(M * \alpha (N))$ <br /> <br /><strong><font color="#0000ff" size="3">4. Алгоритм Флойда. </font></strong> <br />Этот подход для самых ленивых, правда он требует хранить граф явно в виде матрицы смежности. <br />Запускаем алгоритм Флойда и строим матрицу достижимости для каждой пары вершин. В результате если первоначально adj[u][v] указывало на наличие ребра между u и v, то после работы алгоритма adj[u][v] будет указывать на наличие пути между u и v. После чего можно написать DFS двумя вложенными циклами. <br /></font> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">const</font> <font color="#0000ff">int</font> SIZE = 1e3 + 10;</li> <li><font color="#0000ff">int</font> adj[SIZE][SIZE];</li> <li><font color="#0000ff">bool</font> usd[SIZE];</li> <li>...</li> <li><font color="#0000ff">int</font> connected_components_amount_floyd() {</li> <li> </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> k=1;k<=n;++k){</li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i){</li> <li>      <font color="#0000ff">for</font> (<font color="#0000ff">int</font> j=1;j<=n;++j){</li> <li>        <font color="#0000ff">if</font> (adj[i][k] + adj[k][j] == 2)     </li> <li>          adj[i][j] = 1;</li> <li>      }</li> <li>    }</li> <li>  }</li> <li> </li> <li>  <font color="#0000ff">int</font> cnt = 0;</li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<=n;++i) {</li> <li>    <font color="#0000ff">if</font> (!usd[i]) {</li> <li>      ++cnt;</li> <li>      usd[i] = <font color="#0000ff">true</font>;</li> <li>      <font color="#0000ff">for</font> (<font color="#0000ff">int</font> j=1;j<=n;++j) {</li> <li>        <font color="#0000ff">if</font> (adj[i][j] && !usd[j])</li> <li>          usd[j] = <font color="#0000ff">true</font>;</li> <li>      }</li> <li>    }</li> <li>  }</li> <li>  <font color="#0000ff">return</font> cnt;  </li> <li>}</li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> Алгоритм ужасно долгий, но зато пишется довольно просто. Общая сложность $latex O({ N }^{ 3 }) $ <br /><a href="http://www.everfall.com/paste/id.php?g8bhxamsy0b2">Решение</a> <br /> <br /></p> <p><font face="Courier New">Собственно пока и все. Мы рассмотрели 3 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com2tag:blogger.com,1999:blog-9149260308162775442.post-24421282993377870012012-07-13T14:58:00.000+04:002012-07-17T11:17:11.755+04:00Нахождение номера старшего бита числа<div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче </span><a title="Wikipedia" href="http://en.wikipedia.org/wiki/Range_Minimum_Query" target="_blank"><span style="font-family: 'Courier New'">RMQ</span></a><span style="font-family: 'Courier New'">. <br /></span><span style="font-family: 'Courier New'">Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1\leqslant{N}\leqslant{2}^{32}-1$). </span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"><strong><span style="font-size: small">1. naive [O(logN)] </span></strong><span style="font-size: x-small"><font size="2">Первый способ самый простой и очевидный: будем сдвигать N вправо на один бит, пока оно не станет равным 1 (а не 0, так мы сэкономим одну итерацию).</font></span></span> </div> <blockquote style="text-align: left" dir="ltr" trbidi="on"> <ol><code><span style="font-family: 'Courier New'; color: black; font-size: x-small"> <li><font size="2">inline <span style="color: blue">int</span> high_bit_line(UINT n) { </font></li> <li><font size="2">  <span style="color: blue">int</span> res = 0; </font></li> <li><font size="2">  <span style="color: blue">while</span> (n != 1) { </font></li> <li><font size="2">    n >>= 1; </font></li> <li><font size="2">    res++; </font></li> <li><font size="2">  } </font></li> <li><font size="2">  <span style="color: blue">return</span> res; </font></li> <li><font size="2">} </font></li> </span></code></ol> <code><span style="font-family: 'Courier New'; color: black; font-size: x-small"></span><span style="font-size: xx-small"><font size="1"><font size="2">*</font> This source code was highlighted with </font><a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><span style="font-size: xx-small"><font size="1">Source Code Highlighter</font></span></a><font size="1">.</font></span></code></blockquote> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">Сложность первого алгоритма - количество цифр в двоичном представлении N, то есть $latex \log_2{N}$. </span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"> <br /></span><span style="font-family: 'Courier New'; font-size: small"><strong>2. log2 [O(const)] </strong></span><span style="font-size: x-small"><span style="font-family: 'Courier New'"><font size="2">Второй способ математический. Поскольку номер старшего бита - показатель старшей степени двойки, то его номер можно найти с помощью логарифма, округлив его вниз: </font></span></span></div> <blockquote style="text-align: left" dir="ltr" trbidi="on"> <ol><code><span style="font-family: 'Courier New'; color: black"> <li>#include <cmath> </li> <li>  </li> <li><span style="color: blue">const</span> <span style="color: blue">double</span> EPS = 1e-11; </li> <li>inline <span style="color: blue">double</span> log2(<span style="color: blue">double</span> n) { </li> <li>  <span style="color: blue">return</span> log(n) / log(2.0); </li> <li>} </li> <li>inline <span style="color: blue">int</span> high_bit_log2(UINT n) { </li> <li>  <span style="color: blue">return</span> (<span style="color: blue">int</span>)(log2((<span style="color: blue">double</span>)n) + EPS); </li> <li>} </li> </span></code></ol> <code><span style="font-family: 'Courier New'; color: black"></span><span style="font-size: xx-small">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><span style="font-size: xx-small">Source Code Highlighter</span></a>.</span></code></blockquote> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">Вроде бы все классно, но могут возникнуть проблемы с округлением. Поскольку математические операции в cmath могут возвращать неточные значения (например, sqrt(4) = 1.9999...) , то приходится добавлять к их результатам константу. Константа должна быть строго меньше числа, обратного максимальному значению N, иначе это может привести к неправильному результату (например, если к $latex log_2({2}^{32}-1)$ прибавить 10<sup>-9</sup>, то результат будет больше 31). Поэтому в нашем случае я взял 10<sup>-11</sup>, так как $latex \frac 1 {{2}^{32}} \approx {2}*{10}^{-10}$. <br />К сожалению, библиотека cmath в Visual Studio не поддерживает функцию log2, поэтому пришлось делать промежуточную функцию. </span><span style="font-family: 'Courier New'">Сложность вычисления логарифма равна </span><a href="http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BB%D0%BE%D0%B3%D0%B0%D1%80%D0%B8%D1%84%D0%BC#.D0.92.D1.8B.D1.87.D0.B8.D1.81.D0.BB.D0.B8.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.BB.D0.BE.D0.B6.D0.BD.D0.BE.D1.81.D1.82.D1.8C"><span style="font-family: 'Courier New'">константе</span></a><span style="font-family: 'Courier New'">, но она достаточно велика. </span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"> <br /></span><span style="font-family: 'Courier New'"><span style="font-size: small"><strong>3. Binary search [O(log(logN))] </strong></span>В основе этого способа лежит метод бинарного поиска. Будем брать правую часть числа (в двоичном представлении), пока она не равна нулю, а иначе берем левую часть, постепенно деля число пополам, пока не получим 1: </span> <br /></div> <blockquote style="text-align: left" dir="ltr" trbidi="on"> <ol><code><span style="font-family: 'Courier New'; color: black; font-size: x-small"> <li><font size="2">inline <span style="color: blue">int</span> high_bit_bs(UINT n){ </font></li> <li><font size="2">  <span style="color: blue">int</span> size = <span style="color: blue">sizeof</span>(n) * 4; </font></li> <li><font size="2">  <span style="color: blue">int</span> res = 0; </font></li> <li><font size="2">  <span style="color: blue">while</span> (n != 1) { </font></li> <li><font size="2">    <span style="color: blue">int</span> l = n >> size; </font></li> <li><font size="2">    <span style="color: blue">if</span> (l) { </font></li> <li><font size="2">      n = l; </font></li> <li><font size="2">      res += size; </font></li> <li><font size="2">  </font></li> <li><font size="2">    } <span style="color: blue">else</span> { </font></li> <li><font size="2">      n ^= l << size; </font></li> <li><font size="2">    } </font></li> <li><font size="2">    size >>= 1; </font></li> <li><font size="2">  } </font></li> <li><font size="2">  <span style="color: blue">return</span> res; </font></li> <li><font size="2">} </font></li> </span></code></ol> <code><span style="font-family: 'Courier New'; color: black; font-size: x-small"></span><span style="font-size: xx-small"><font size="1">* This source code was highlighted with </font><a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><span style="font-size: xx-small"><font size="1">Source Code Highlighter</font></span></a><font size="1">.</font></span></code></blockquote> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">Рассмотрим применение этого алгоритма к числу 1234567890.</span> </div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">$latex 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 | 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0$ <span style="font-size: x-small"><span style="font-size: x-small"><font size="2">res = 0; size = 16; </font></span></span></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"><span style="font-size: x-small"><span style="font-size: x-small"></span></span></span><span style="font-family: 'Courier New'">$latex 0 1 0 0 1 0 0 1|1 0 0 1 0 1 1 0$ <span style="font-size: x-small"><span style="font-size: x-small"><font size="2">res = 16; size = 8; </font></span></span></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"><span style="font-size: x-small"><span style="font-size: x-small"></span></span></span><span style="font-family: 'Courier New'">$latex 0 1 0 0|1 0 0 1$ <span style="font-size: x-small"><span style="font-size: x-small"><font size="2">res = 24; size = 4; </font></span></span></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"><span style="font-size: x-small"><span style="font-size: x-small"></span></span></span><span style="font-family: 'Courier New'">$latex 0 1|0 0$ <span style="font-size: x-small"><span style="font-size: x-small"><font size="2">res = 28; size = 2; </font></span></span></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"><span style="font-size: x-small"><span style="font-size: x-small"></span></span></span><span style="font-family: 'Courier New'">$latex 0|1$ <span style="font-size: x-small"><span style="font-size: x-small"><font size="2">res = 30; size = 1; <br /></font></span></span></span><span style="font-family: 'Courier New'">Сложность этого способа равна логарифму от числа битов N, то есть $latex \log _{ 2 } (\log _{ 2 }{ N } )$. </span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"> <br /></span><strong><span style="font-family: 'Courier New'; font-size: small">4. Binary search with mask [O(log(log(N)))]</span></strong> <br /><span style="font-family: 'Courier New'">Да, я не ошибся, сложность четвертого алгоритма почти равна сложности третьего, так как этот способ является всего лишь небольшой оптимизацией предыдущего. В третьем алгоритме мы находим правую часть числа через левую (строка 9). Здесь мы затрачиваем две операции: битового сдвига и исключающего ИЛИ (XOR). Эти операции можно заменить на сложение и И (AND), добавив константный массив масок: </span></div> <blockquote> <div style="text-align: left" dir="ltr" trbidi="on"><code><span style="font-family: 'Courier New'; color: black"><span style="color: blue">const</span> <span style="color: blue">int</span> MASK_R[6] = {0x0000FFFF, 0x000000FF, 0x0000000F, 0x00000003, 0x00000001}; </span></code> <br /></div> </blockquote> <code><span style="font-family: 'Courier New'; color: black; font-size: x-small"></span></code> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'"></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">Немного исправив код третьего способа, получаем:</span> </div> <blockquote style="text-align: left" dir="ltr" trbidi="on"> <ol><code><span style="font-family: 'Courier New'; color: black; font-size: x-small"> <li><font size="2">inline <span style="color: blue">int</span> high_bit_bsm(UINT n){ </font></li> <li><font size="2">  <span style="color: blue">int</span> size = <span style="color: blue">sizeof</span>(n)*4; </font></li> <li><font size="2">  <span style="color: blue">int</span> res = 0; </font></li> <li><font size="2">  <span style="color: blue">int</span> m = 0; </font></li> <li><font size="2">  <span style="color: blue">while</span> (n != 1) { </font></li> <li><font size="2">    <span style="color: blue">int</span> l = n >> size; </font></li> <li><font size="2">    <span style="color: blue">if</span> (l) { </font></li> <li><font size="2">      n = l; </font></li> <li><font size="2">      res += size; </font></li> <li><font size="2">    } <span style="color: blue">else</span> { </font></li> <li><font size="2">      n &= MASK_R[m]; </font></li> <li><font size="2">    } </font></li> <li><font size="2">    size >>= 1; </font></li> <li><font size="2">    m++; </font></li> <li><font size="2">  } </font></li> <li><font size="2">  <span style="color: blue">return</span> res; </font></li> <li><font size="2">} </font></li> </span></code></ol> <code><span style="font-family: 'Courier New'; color: black; font-size: x-small"></span><span style="font-size: xx-small"><font size="1">* This source code was highlighted with </font><a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><span style="font-size: xx-small"><font size="1">Source Code Highlighter</font></span></a><font size="1">.</font></span></code></blockquote> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'">Правда, в некоторых случаях эта оптимизация будет работать дольше, чем оригинал, поскольку операция сложения выполняется при каждом проходе цикла while. <br /> <br /></span></div> <div style="text-align: left" dir="ltr" trbidi="on"><span style="font-family: 'Courier New'; font-size: small"><u><strong>Выводы:</strong></u></span><span style="font-family: 'Courier New'; font-size: small"><span style="font-size: x-small"><font size="2"> Подход с бинарным поиском  дает наилучший результат. <br />Если нужно решать поставленную задачу на ограниченном диапазоне, который можно хранить в памяти, то лучше динамикой подсчитать позицию старшего единичного бита для каждого числа в диапазоне. <br />Эта идея хорошо описана в </font><a href="http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_RMQ_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B6%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D0.BD.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87.D0.B5_RMQ"><strong><u><font size="2">вики конспектах ИТМО</font></u></strong></a><font size="2">(Раздел “Применение к задаче RMQ”).</font></span></span></div> Danilhttp://www.blogger.com/profile/09911645882342738576noreply@blogger.com19tag:blogger.com,1999:blog-9149260308162775442.post-26981374845836392462012-05-15T13:55:00.001+04:002012-06-24T14:34:57.114+04:00Problem 377 [ProjectEuler.net]<p><img style="background-image: none; border-right-width: 0px; padding-left: 0px; padding-right: 0px; display: inline; float: right; border-top-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 0px" border="0" align="right" src="https://lh5.googleusercontent.com/-gs2197c7BCc/T7IkCYwZCfI/AAAAAAAAB7A/zrSOjT-cyjA/s215/algo-letter-%25D0%2594%25D0%25B0%25D0%25BD%25D0%25B8%25D0%25BB.png" /></p> <p> </p> <p> </p> <p> </p> <p align="justify"><a href="http://projecteuler.net/problem=377"><strong><font face="Courier New">[Условие задачи]</font></strong></a><font face="Courier New"> <br />Решать задачу начнем с простого. <br />Для начала найдем $latex f(13)$. Это можно сделать несложным рекурсивно-комбинаторным алгоритмом, который оставим для самостоятельной проработки. <br />Итог: $latex f(13)=3835856884757$ <br /> <br />Получить $latex f(169)$ тем же алгоритмом вряд ли получится. <br />Далее будет описан алгоритм, который может это сделать. Представленную логику можно применить для любой степени 13. <br /> <br />Введем интуитивно понятные термины: <br /><strong><font color="#ff0000">Префикс длины L числа N</font></strong> – первые L цифр (старшие разряды) числа N. <br /><font color="#ff0000"><strong>Постфикс длины L числа N</strong></font> – последние L цифр (младшие разряды) числа N. <br /><strong><font color="#ff0000">Сумма префикса/постфикса</font></strong> – сумма цифр, входящих в префикс/постфикс. <br />Под <strong><font color="#ff0000">промежуточным числом</font></strong> будем понимать число, которое используется при подсчете значения $latex f({ 13 }^{ k })$, так например число 1121 является промежуточным для $latex f(5)$ <br />По условию задачи нужно найти последние 9 цифр ответа. Минимальным постфиксом длины 9 промежуточного числа для $latex f(169)$ является 111111111, а максимальным - 999999999. Т.к. в условии оговорено, что в состав промежуточного числа не входит ноль, то можно сделать утверждение, что количество различных постфиксов длины 9 для промежуточных чисел будет ровно $latex { 9 }^{ 9 }=387 420 489$, а различных сумм заданных постфиксов $latex 81-9+1=73$. <br />Для фиксированного постфикса промежуточного числа найдем количество возможных префиксов. Пусть сумма постфикса равна $latex S$, тогда сумма префикса равна $latex 169-S$. <br />Пусть $latex G(N)$ – функция которая возвращает количество всевозможных префиксов, сумма цифр которых равна $latex N$. Остаточные знания нам навевают понятие </font><a href="http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0"><strong><font face="Courier New">Разбиение числа на слагаемые</font></strong></a><font face="Courier New"><strong>, </strong>но в нашем случае нужно использовать не разбиение, а </font><a href="http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB)"><strong><font face="Courier New">Композицию числа на слагаемые</font></strong></a><font face="Courier New">. <br />В общем случае количество композиций числа $latex N$ на ненулевые слагаемые равно $latex { 2 }^{ N-1 }$, но это только в том случае, если нет ограничений на слагаемые. В нашем же случае каждое ненулевое слагаемое должно не превышать 9. <br />Для того, чтобы найти $latex G(N)$ вспомним старую задачу </font><a href="http://acmp.ru/index.asp?main=task&id_task=11"><strong><font face="Courier New">Зайчик</font></strong></a><font face="Courier New">. Если вникнуть, то можно увидеть, что в этой задаче как раз и ищется функция $latex G(N)$ с ограничением на максимальное слагаемое. <br />Получаем: $latex \displaystyle G(N)=\left\{\begin{matrix}1, N=0\\ 2^{N-1}, 1<=N<=9\\ \sum_{i=1}^{9}G(N-i), N>9\end{matrix}\right.$ <br />Последняя формула выглядит весьма угрожающе. В </font><a href="http://oeis.org/A104144"><strong><font face="Courier New">интернетах</font></strong></a><font face="Courier New"> находим, что $latex G(N)$ образует последовательность чисел, называемых </font><font size="3" face="Courier New"><strong>Fibonacci 9-step numbers. <br /></strong></font><font size="2" face="Courier New">И вот наверное сейчас мы подошли к самому интересному. $latex G(169-9)$ мы еще сможем найти, а как быть если степень 13 будет велика. Нужен способ, который находит G(N) быстрее чем за O(N). <br />В книге “Программирование. Теоремы и задачи”(А.Шень) приводится пример, как можно найти N-ое число Фибоначчи за O(logN) с помощью быстрого возведения в степень начальной матрицы. Тот же принцип можно использовать и здесь. Приведу фрагмент, по которому можно понять общую логику:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>typedef unsigned <font color="#0000ff">long</font> <font color="#0000ff">long</font> ULL; </li> <li><font color="#0000ff">const</font> ULL OSN = (ULL)1e9; </li> <li><font color="#0000ff">const</font> ULL BASE[SIZE][SIZE] = { </li> <li>  {128, 64, 32, 16, 8, 4, 2, 1, 1}, </li> <li>  {64, 32, 16, 8, 4, 2, 1, 1, 0}, </li> <li>  {32, 16, 8, 4, 2, 1, 1, 0, 0}, </li> <li>  {16,  8, 4, 2, 1, 1, 0, 0, 0}, </li> <li>  {8,  4, 2, 1, 1, 0, 0, 0, 0}, </li> <li>  {4,  2, 1, 1, 0, 0, 0, 0, 0}, </li> <li>  {2,  1, 1, 0, 0, 0, 0, 0, 0}, </li> <li>  {1,  1, 0, 0, 0, 0, 0, 0, 0}, </li> <li>  {1,  0, 0, 0, 0, 0, 0, 0, 0} </li> <li>}; </li> <li><font color="#0000ff">const</font> ULL A[SIZE][SIZE] = { </li> <li>  {1, 1, 0, 0, 0, 0, 0, 0, 0}, </li> <li>  {1, 0, 1, 0, 0, 0, 0, 0, 0}, </li> <li>  {1, 0, 0, 1, 0, 0, 0, 0, 0}, </li> <li>  {1, 0, 0, 0, 1, 0, 0, 0, 0}, </li> <li>  {1, 0, 0, 0, 0, 1, 0, 0, 0}, </li> <li>  {1, 0, 0, 0, 0, 0, 1, 0, 0}, </li> <li>  {1, 0, 0, 0, 0, 0, 0, 1, 0}, </li> <li>  {1, 0, 0, 0, 0, 0, 0, 0, 1}, </li> <li>  {1, 0, 0, 0, 0, 0, 0, 0, 0} </li> <li>}; </li> <li><font color="#0000ff">const</font> ULL E[SIZE][SIZE] = { </li> <li>  {1, 0, 0, 0, 0, 0, 0, 0, 0}, </li> <li>  {0, 1, 0, 0, 0, 0, 0, 0, 0}, </li> <li>  {0, 0, 1, 0, 0, 0, 0, 0, 0}, </li> <li>  {0, 0, 0, 1, 0, 0, 0, 0, 0}, </li> <li>  {0, 0, 0, 0, 1, 0, 0, 0, 0}, </li> <li>  {0, 0, 0, 0, 0, 1, 0, 0, 0}, </li> <li>  {0, 0, 0, 0, 0, 0, 1, 0, 0}, </li> <li>  {0, 0, 0, 0, 0, 0, 0, 1, 0}, </li> <li>  {0, 0, 0, 0, 0, 0, 0, 0, 1} </li> <li>}; </li> <li>ULL G(ULL n) { </li> <li>  ULL res = 0; </li> <li>  <font color="#0000ff">if</font> (n <= 9) { </li> <li>    res = _pow(2, n - 1); </li> <li>  } </li> <li>  <font color="#0000ff">else</font> { </li> <li>    matrix AN = E, cur = A; </li> <li>    n -= SIZE - 2; </li> <li>    <font color="#0000ff">while</font> (n) { </li> <li>      <font color="#0000ff">if</font> (n & 1) </li> <li>        AN = AN * cur; </li> <li>      cur = cur * cur; </li> <li>      n >>= 1; </li> <li>    } </li> <li>    matrix fin = matrix(BASE) * AN; </li> <li>    res = fin.data[0][1]; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> res; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p align="justify"><font face="Courier New">Все нужные кирпичики описаны. Теперь соберем их в общую картину.  <br />Последние 9 цифр суммы всех промежуточных чисел для $latex f(169)$ c фиксированным постфиксом можно найти по формуле: $latex postfix*G(169-sum(postfix))mod1e9$. Перебрав все возможные постфиксы можно найти и само значение $latex f(169)$. Для всех остальных степеней 13, как уже говорилось ранее, применима такая же логика.  <br />Можно предложить несколько схем, ускоряющих общие вычисления. Но их мы оставим для самостоятельной проработки.</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-84737094574359361982012-03-25T23:25:00.001+04:002012-03-25T23:35:28.694+04:00Расстановка знаков в арифметическом выражении<p align="justify"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong><font face="Courier New">[Все темы по размещениям]</font></strong></a> <br /> <br /><font face="Courier New"><strong><u>Задача</u></strong>: </font><a href="http://contester.tsure.ru/index.php?page=ViewTask.php&EditID=106"><strong><font face="Courier New">155. Дешифровка выражения(contester.tsure.ru)</font></strong></a><font face="Courier New"> </font><a href="https://sites.google.com/site/slipstak2/155.pdf?attredirects=0&d=1"><strong><u><font face="Courier New">[Условие]</font></u></strong></a> <br /><font face="Courier New"><strong><u>Предварительные темы:</u></strong>    </font><a href="http://cppalgo.blogspot.com/2012/03/blog-post_20.html"><strong><font face="Courier New">[Генерация всех размещений с повторениями рекурсивным способом]</font></strong></a> <br /><font face="Courier New">                         </font><a href="http://cppalgo.blogspot.com/2012/03/blog-post_22.html"><strong><font face="Courier New">[Генерация следующего размещения с повторениями]</font></strong></a> <br /><strong><font face="Courier New">                         </font></strong><a href="http://algolist.manual.ru/maths/misc/revpn.php"><strong><font face="Courier New">[Подсчет арифметического выражения(обратная польская нотация)]</font></strong></a> <br /><strong><font face="Courier New"><u>Дополнительная практика</u>: </font></strong><a href="http://cppalgo.blogspot.com/2011/08/14-25-2011.html"><strong><font face="Courier New">Задачи для подсчета арифметического выражения (см. занятие 4 - архив)</font></strong></a> <br /> <br /><font face="Courier New">Итак, имеется корректное арифметическое выражение вида (9?8)?(0?3)?2=-25, вместо знаков ? необходимо поставить одну из 4 операций +,-,*,/ так, чтобы выражение стало правильным. Если такого сделать нельзя, то нужно вывести “No solution.”. Для удобства гарантируется, что в левой части выражения все числа являются цифрами и отсутствуют унарные знаки. В правой же части может быть любое число по модулю не превышающее 10<sup>15</sup>. <br /> <br />Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10 <br />Алфавит знаков содержит четыре элемент: {+,-,/,*}. <br />Количество позиций в размещении(количество знаков ? в выражении): 2 <br />Общее количество размещений: 4<sup></sup><sup>2</sup>=16 <br /> <br />Сгенерируем все <a href="http://cppalgo.blogspot.com/2012/03/blog-post_20.html"><strong>размещения с повторениями рекурсивным способом</strong></a> и получим все возможные комбинации исходного арифметического выражения:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>2+(3+4)=9 </li> <li>2+(3-4)=1 </li> <li>2+(3*4)=14 </li> <li>2+(3/4)=2 </li> <li>2-(3+4)=-5 </li> <li>2-(3-4)=3 </li> <li>2-(3*4)=-10 </li> <li>2-(3/4)=2 </li> <li>2*(3+4)=14 </li> <li>2*(3-4)=-2 </li> <li>2*(3*4)=24 </li> <li>2*(3/4)=0 </li> <li>2/(3+4)=0 </li> <li>2/(3-4)=-2 </li> <li>2/(3*4)=0 </li> <li>2/(3/4)=NAN </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p align="justify"><font face="Courier New">Значение NAN обозначает, что в выражении присутствует деление на ноль. Сам подсчет будем делать с помощью перевода в <a href="http://algolist.manual.ru/maths/misc/revpn.php"><strong>обратную польскую запись</strong></a>, подсчетом значения на лету. <br />Подсчет значения на лету можно сделать так:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">string</font> opers = <font color="#a31515">"+-*/"</font>; </li> <li><font color="#0000ff">bool</font> calc(INT &f, INT &s, <font color="#0000ff">char</font> op, INT &res) { </li> <li>  <font color="#0000ff">switch</font>(op) { </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'+'</font> : res = f + s; <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'-'</font> : res = f - s; <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'*'</font> : res = f * s; <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'/'</font> : <font color="#0000ff">if</font> (s != 0) { </li> <li>            res = f / s; </li> <li>            <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>          } </li> <li>          <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>} </li> <li><font color="#0000ff">bool</font> calc_last (stack<INT> &val, stack<<font color="#0000ff">char</font>> &oper) { </li> <li>  INT s = val.top(); val.pop(); </li> <li>  INT f = val.top(); val.pop(); </li> <li>  INT r = -1; </li> <li>  <font color="#0000ff">if</font> (calc(f,s,oper.top(),r)) { </li> <li>    val.push(r); </li> <li>    oper.pop(); </li> <li>    <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>} </li> <li><font color="#0000ff">int</font> prior(<font color="#0000ff">char</font> op) { </li> <li>  <font color="#0000ff">switch</font>(op) { </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'+'</font>: </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'-'</font>: <font color="#0000ff">return</font> 0; </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'*'</font>: </li> <li>    <font color="#0000ff">case</font> <font color="#a31515">'/'</font>: <font color="#0000ff">return</font> 1; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> -1; </li> <li>} </li> <li><font color="#0000ff">bool</font> is_num(<font color="#0000ff">char</font> c) { </li> <li>  <font color="#0000ff">return</font> <font color="#a31515">'0'</font> <= c && c <= <font color="#a31515">'9'</font>; </li> <li>} </li> <li><font color="#0000ff">bool</font> calc(<font color="#0000ff">const</font> <font color="#0000ff">string</font> &expr, INT &res) { </li> <li>  stack<INT> val; </li> <li>  stack<<font color="#0000ff">char</font>> oper; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<expr.size();++i) { </li> <li>    <font color="#0000ff">if</font> (is_num(expr[i])) </li> <li>      val.push(expr[i] - <font color="#a31515">'0'</font>); </li> <li>    <font color="#0000ff">else</font> <font color="#0000ff">if</font> (expr[i] ==<font color="#a31515">'('</font>) </li> <li>      oper.push(expr[i]); </li> <li>    <font color="#0000ff">else</font> <font color="#0000ff">if</font> (expr[i] == <font color="#a31515">')'</font>) { </li> <li>      <font color="#0000ff">while</font> (oper.top() != <font color="#a31515">'('</font>) { </li> <li>        <font color="#0000ff">if</font> (!calc_last(val, oper)) </li> <li>          <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>      } </li> <li>      oper.pop(); </li> <li>    } </li> <li>    <font color="#0000ff">else</font> { <font color="#008000">// expr[i] - операция</font> </li> <li>      <font color="#0000ff">while</font> (!oper.empty()) { </li> <li>        <font color="#0000ff">if</font> (prior(oper.top()) >= prior(expr[i])) { </li> <li>          <font color="#0000ff">if</font> (!calc_last(val, oper)) </li> <li>            <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>        } </li> <li>        <font color="#0000ff">else</font> <font color="#0000ff">break</font>; </li> <li>      } </li> <li>      oper.push(expr[i]); </li> <li>    } </li> <li>  } </li> <li>  <font color="#0000ff">while</font> (!oper.empty()) { </li> <li>    <font color="#0000ff">if</font> (!calc_last(val,oper)) </li> <li>      <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>  } </li> <li>  res = val.top(); </li> <li>  <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p align="justify"><font face="Courier New"><strong><u>Исходный код</u></strong>: </font><a href="http://www.everfall.com/paste/id.php?0rdl0ypbcnlm"><strong><font face="Courier New">здесь</font></strong></a><font face="Courier New"> <br /> <br />Отправляем в систему проверки на contester.tsure.ru и получаем вердикт: TLE9. =)) <br />В худшем случае количество операций равно 10, значит общее количество генерируемых размещений будет 4<sup>10</sup>=1048576. Получается, что приведенный фрагмент кода подсчета значения выражения на лету будет запускаться более 1 млн. раз. Т.к. в данной задаче нам придется генерировать все размещения, то естественным путем оптимизации исходного решения – минимизировать количество построений обратной польской записи. <br />Рассмотрим несколько выражений и их обратные польские записи. <br /> <br /><strong>Номер     Выражение           Обратная польская запись <br /></strong>1         5*2+3-(7+2)/2       5 2 * 3 + 7 2 + 2 / - <br />2         5/2-3+(7-2)*2       5 2 / 3 – 7 2 – 2 * +</font><font face="Courier New">  <br />3         5+2*3/(7*2)-2       5 2 3 * 7 2 * / + 2 - <br />4         5-2/3*(7/2)+2       5 2 3 / 7 2 / * – 2 +</font></p> <p align="justify"><font face="Courier New">Подсчет выражения по обратной польской записи осуществляется за 1 проход. <br />Т.к. соответствующие операции в выражениях 1 и 2 имеют одинаковые приоритеты, то для них получаются две обратные польские записи, которые можно считать подобными. Тоже самое можно наблюдать для выражений 3 и 4. <br /><strong><font color="#ff0000">Две обратные польские записи назовем подобными, если соответствующие операции имеют одинаковый приоритет.</font></strong> <br />Все операции можно разбить на две группы: <br />1. С меньшим приоритетом(0) : + , - <br />2. С большим приоритетом(1) : * , / <br /> <br />Поэтому изначально можно сгенерировать до 2<sup>10</sup>=1024 размещений из приоритетов [0 и 1]. При этом, если на место операции выпадает 0 в размещении это говорит о том, что на ее место будут последовательно поставлены операции с нулевым приоритетом, т.е + или –. <br /></font><font face="Courier New"><strong><font color="#ff0000">Для выражений с одинаковыми размещениями приоритетов получаются подобные обратные польские записи. <br /></font></strong> <br />Рассмотрим выражение:              5?2?3?(7?2)?2 <br />Текущее размещение из приоритетов: {1, 0, 0, 0, 1}  <br />Обратная польская запись:          5 2 [1] 3 [0] 7 2 [0] 2 [1] [0], где [x] – операция с приоритетом x <br />Как можно заметить, текущая обратная польская запись соответствует 1 и 2 выражению из таблицы. <br /> <br />Далее подумаем, как можно перебрать конкретные знаки, с уже расставленными приоритетами операций. <br />Для текущего размещения R можно поставить в соответствие два размещения F и S. <br />При этом длина F равна количеству нулей в размещении R, а длина S – количеству единиц. <br />Элементы множества F будут состоять из операций с нулевым приоритетом, а S – из элементом с единичным приоритетом. <br /> <br /><strong>Номер   Выражение        R              F           S <br /></strong>1       5*2+3-(7+2)/2    {1,0,0,0,1}    {+,-,+}     {*,/} <br />2       5/2-3+(7-2)*2    {1,0,0,0,1}    {-,+,-}     {/,*} <br />3       5+2*3/(7*2)-2    {0,1,1,1,0}    {+,-}       {*,/,*} <br />4       5-2/3*(7/2)+2    {0,1,1,1,0}    {-,+}       {/,*,/}</font></p> <p align="justify"><font face="Courier New">Все вышеизложенную идею можно описать <a href="http://www.everfall.com/paste/id.php?rdasq1peqw2n"><strong>так</strong></a>. При этом получается, что в худшем случае придется генерировать 2<sup>10</sup>=1024 обратных польских записей вместо 4<sup></sup><sup>10</sup>=1048576. Благодаря этим преобразованием последнее решение уложилось в 1.5 секунды на сервере проверки. <br /> <br />В целях рефакторинга второй реализации можно скрестить генерацию размещений R и {F,S}.</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-19199731039389414912012-03-23T00:20:00.001+04:002012-03-23T00:21:19.819+04:00Получение номера по размещению с повторениями<p align="justify"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong><font face="Courier New">[Все темы по размещениям]</font></strong></a> <br /> <br /><font face="Courier New"><strong><u>Теория</u></strong>: Окулов. Дискретная математика. 2008. <br /><strong><u>Практика</u></strong>: <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=82#1"><strong>[82. Все строки длины n из k различных символов]</strong></a> <br /> <br />Ранее мы научились <a href="http://cppalgo.blogspot.com/2012/03/blog-post_23.html"><strong>генерировать размещение с повторениями по номеру</strong></a>. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему. <br /> <br />Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке. <br />20221112<sub>3</sub>=<strong><font color="#ff0000">2</font></strong>*2187+<strong><font color="#ff0000">0</font></strong>*729+<strong><font color="#ff0000">2</font></strong>*243+<strong><font color="#ff0000">2</font></strong>*81+<strong><font color="#ff0000">1</font></strong>*27+<strong><font color="#ff0000">1</font></strong>*9+<strong><font color="#ff0000">1</font></strong>*3+<strong><font color="#ff0000">2</font></strong>*1=4374+486+162+27+9+3+2=5063<sub>10</sub>. <br /> <br />Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064. <br /></font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>typedef unsigned <font color="#0000ff">long</font> <font color="#0000ff">long</font> ULL;</li> <li>ULL get_num_by_placement_rep(<font color="#0000ff">const</font> vector<<font color="#0000ff">int</font>> &cur, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> k) {</li> <li>  ULL num = 0;</li> <li>  ULL step = 1;</li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=cur.size()-1;i>=0;--i) {</li> <li>    num += cur[i] * step;</li> <li>    step *= k;</li> <li>  }</li> <li>  <font color="#0000ff">return</font> num;</li> <li>}</li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-11839198090611115462012-03-23T00:00:00.001+04:002012-03-23T00:00:58.938+04:00Генерация размещения с повторениями по номеру<p><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong><font face="Courier New">[Все темы по размещениям]</font></strong></a> <br /> <br /><font face="Courier New"><strong><u>Теория</u></strong>: Окулов. Дискретная математика. 2008 <br /><strong><u>Практика</u></strong>: <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=82#1"><strong>[82. Все строки длины n из k различных символов]</strong></a> <br /> <br />Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке. <br />Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>00 </li> <li>01 </li> <li>02 </li> <li>03 </li> <li>10 </li> <li>11 </li> <li>12 </li> <li>13 </li> <li>20 </li> <li>21 </li> <li>22 </li> <li>23 </li> <li>30 </li> <li>31 </li> <li>32 </li> <li>33 </li> </ol> </font></code></blockquote> <p align="justify"><font face="Courier New">Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания. <br />Проверим наше утверждение на размещении “31”: 31<sub>4</sub>=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0. <br />Данная логика отображена в следующей функции:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>typedef unsigned <font color="#0000ff">long</font> <font color="#0000ff">long</font> ULL;</li> <li><font color="#0000ff">void</font> gen_placement_rep_by_num(vector<<font color="#0000ff">int</font>> &cur, ULL num, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> k) {</li> <li>  cur.assign(n,0);</li> <li>  <font color="#0000ff">int</font> pos = n - 1;</li> <li>  <font color="#0000ff">while</font> (num) {</li> <li>    cur[pos--] = num % k;</li> <li>    num /= k;</li> <li>  }</li> <li>}</li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New">Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-79431547100118028002012-03-22T23:22:00.001+04:002012-03-22T23:22:52.887+04:00Генерация следующего и предыдущего размещения с повторениями<p><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><font face="Courier New"><strong>[Все темы по размещениям]</strong></font></a> <br /> <br /><font face="Courier New"><strong><u>Теория</u></strong>: Окулов. Дискретная математика. 2008. <br /><strong><u>Практика</u></strong>: <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=82#1"><strong>[82. Все строки длины n из k различных символов]</strong></a> <br /></font> <br /><font face="Courier New">Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке. <br /> <br />R<sub>i</sub> = {1, 5, 6, 4, 6}; n = 5; k = 7 <br />R<sub>i+1</sub> = {1, 5, 6, 5, 0} <br /> <br />Для генерации следующего размещения будем пользоваться простым правилом: <br />Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">bool</font> next_placement_rep(vector<<font color="#0000ff">int</font>> &cur, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> k) { </li> <li>  <font color="#0000ff">int</font> r = 1; </li> <li>  <font color="#0000ff">int</font> pos = n-1; </li> <li>  <font color="#0000ff">while</font> (pos>=0 && r) { </li> <li>    cur[pos]++; </li> <li>    r = cur[pos] == k; </li> <li>    <font color="#0000ff">if</font> (r) cur[pos] = 0; </li> <li>    --pos; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> !r; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New"><strong><u>Полная реализация</u></strong>: <a href="http://www.everfall.com/paste/id.php?b0xfv4y9cpwf"><strong>здесь</strong></a> <br /> <br />Генерация предыдущего размещения делается по аналогичной схеме:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">bool</font> prev_placement_rep(vector<<font color="#0000ff">int</font>> &cur, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> k) { </li> <li>  <font color="#0000ff">int</font> r = 1; </li> <li>  <font color="#0000ff">int</font> pos = n-1; </li> <li>  <font color="#0000ff">while</font> (pos >=0 && r) { </li> <li>    cur[pos]--; </li> <li>    r = cur[pos] == -1; </li> <li>    <font color="#0000ff">if</font> (r) cur[pos] = k-1; </li> <li>    --pos; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> !r; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-10007355052648104422012-03-20T14:59:00.001+04:002012-03-22T23:23:56.428+04:00Генерация всех размещений с повторениями рекурсивным способом<p><font face="Courier New"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong>[Все темы по размещениям]</strong></a> <br /> <br /><strong><u>Теория</u></strong>: Окулов. Дискретная математика. 2008 <br /><strong><u>Практика</u></strong>: <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=82#1"><strong>Все строки длины n из k различных символов</strong></a> <br /> <br />Пусть задан алфавит из K первых цифр, начиная с 0. Необходимо сгенерировать все размещения с повторениями длины N для элементов данного алфавита. Другими словами для N = 2 и K = 4 получаем:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>00 </li> <li>01 </li> <li>02 </li> <li>03 </li> <li>10 </li> <li>11 </li> <li>12 </li> <li>13 </li> <li>20 </li> <li>21 </li> <li>22 </li> <li>23 </li> <li>30 </li> <li>31 </li> <li>32 </li> <li>33 </li> </ol> </font></code></blockquote> <p><font face="Courier New">Генерация такой последовательности не должно составить большого труда:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">void</font> gen(<font color="#0000ff">int</font> pos) { </li> <li>  <font color="#0000ff">if</font> (pos == n) { </li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<n;++i) </li> <li>      printf(<font color="#a31515">"%d"</font>,cur[i]); </li> <li>    printf(<font color="#a31515">"\n"</font>); </li> <li>    <font color="#0000ff">return</font>; </li> <li>  } </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<k;++i) { </li> <li>    cur[pos] = i; </li> <li>    gen(pos+1); </li> <li>  } </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New">Изначально функция gen запускается с параметром 0. <br />Полное решение: <a href="http://www.everfall.com/paste/id.php?1lr8djmfaeh3"><strong>здесь</strong></a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-47326623833257951692012-03-16T23:27:00.001+04:002012-03-22T23:48:06.662+04:00Генерация размещения без повторений по номеру за O(N*N)<p><font face="Courier New"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong>[Все темы по размещениям]</strong></a> <br /> <br /><strong><u>Теория</u></strong>: Окулов. Программирование в алгоритмах. 2004 <br /><strong><u>Практика</u></strong>: <strong><a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3784">[3784. Генерация размещений]</a></strong> <br /> <br />Ранее мы рассмотрели <a href="http://cppalgo.blogspot.com/2012/03/onn.html"><strong>получение номера по размещению</strong></a> за O(N*N). В данной же задаче нужно сделать все с точностью до наоборот:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">int</font> placement_amount(<font color="#0000ff">int</font> n, <font color="#0000ff">int</font> m) { </li> <li>  <font color="#0000ff">int</font> res = 1; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i = n; i >= n-m+1; --i) { </li> <li>    res *= i; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> res; </li> <li>} </li> <li><font color="#0000ff">void</font> gen_placement_by_num(<font color="#0000ff">int</font> num, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> m, vector<<font color="#0000ff">int</font>> &mas) { </li> <li>  vector<<font color="#0000ff">bool</font>> usd(n,<font color="#0000ff">false</font>); </li> <li>  <font color="#0000ff">int</font> _n = n-1, _m = m-1; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<m;++i) { </li> <li>    <font color="#0000ff">int</font> block_cnt = num / placement_amount(_n,_m); </li> <li>    num -= block_cnt * placement_amount(_n,_m); </li> <li>    <font color="#0000ff">int</font> pos = 0; </li> <li>    ++block_cnt; </li> <li>    <font color="#0000ff">while</font> (block_cnt) { </li> <li>      <font color="#0000ff">if</font> (!usd[pos]) </li> <li>        --block_cnt; </li> <li>      ++pos; </li> <li>    } </li> <li>    usd[pos-1] = <font color="#0000ff">true</font>; </li> <li>    mas[i] = pos; </li> <li>    --_n; --_m; </li> <li>  } </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New">При многократном вызове функции gen_placement_by_num можно сделать препроцессинг и не использовать функцию placement_amount.</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-28898105055315109372012-03-16T22:24:00.001+04:002012-03-16T22:24:34.841+04:00Получение номера по размещению без повторений за O(N*N)<p><font face="Courier New"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong>[Все темы по размещениям]</strong></a> <br /> <br /><strong><u>Теория</u></strong>: Окулов. Программирование в алгоритмах. 2004. <br /><strong><u>Практика</u></strong>: <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=192"><strong>192. По размещению!</strong></a> <br /> <br />Рассмотрим все размещения для n = 4 и m = 3:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font size="3"><strong><font style="background-color: #ffffff"><font color="#ff0000">1</font><font color="#000000">23</font></font></strong></font> </li> <li><font size="3"><strong><font style="background-color: #ffffff"><font color="#ff0000">1</font><font color="#000000">24</font></font></strong></font> </li> <li><font size="3"><strong><font style="background-color: #ffffff"><font color="#ff0000">1</font><font color="#000000">32</font></font></strong></font> </li> <li><font size="3"><strong><font style="background-color: #ffffff"><font color="#ff0000">1</font><font color="#000000">34</font></font></strong></font> </li> <li><font size="3"><strong><font style="background-color: #ffffff"><font color="#ff0000">1</font><font color="#000000">42</font></font></strong></font> </li> <li><font size="3"><strong><font style="background-color: #ffffff"><font color="#ff0000">1</font><font color="#000000">43</font></font></strong></font> </li> <li><font size="3"><strong><font color="#0000ff">2</font>13</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">2</font>14</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">2</font>31</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">2</font>34</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">2</font>41</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">2</font>43</strong></font> </li> <li><font size="3"><strong><font color="#ff0000">3</font>12</strong></font> </li> <li><font size="3"><strong><font color="#ff0000">3</font>14</strong></font> </li> <li><font size="3"><strong><font color="#ff0000">3</font>21</strong></font> </li> <li><font size="3"><strong><font color="#ff0000">3</font>24</strong></font> </li> <li><font size="3"><strong><font color="#ff0000">3</font>41</strong></font> </li> <li><font size="3"><strong><font color="#ff0000">3</font>42</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">4</font>12</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">4</font>13</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">4</font>21</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">4</font>23</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">4</font>31</strong></font> </li> <li><font size="3"><strong><font color="#0000ff">4</font>32</strong></font> </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p align="justify"><font face="Courier New">Можно заметить, что все размещения можно разбить на 4(n) блока. Элементы первого блока начинаются на 1, второго - на 2 и т.д. В каждом блоке находится равное количество элементов равное (n-1)!/(n-m)!. В нашем случае по 6 элементов. <br />Зная значения n и m и текущее размещение, можно найти размер блока <strong>B</strong> и определить интервал [L,R], в котором лежат все размещения, начинающиеся на общий первый элемент. <br />L = B * LESS, где LESS - количество элементов алфавита, меньших первого элемента размещения. <br />R = L + B – 1. <br />Далее извлекаем первый элемент размещения из общего алфавита и решает ту же задачу для n`=n-1 и m`=m-1. Рассмотрим идею на конкретном примере: <br />Пусть n = 9, m = 7. Размещение R = {6, 3, 8, 1, 9, 4, 7}.</font></p> <font face="Courier New"> <table border="0" cellspacing="0" cellpadding="2" width="737"><tbody> <tr> <td valign="top" width="93"><strong>Итерация</strong></td> <td valign="top" width="106"><strong>Размещение</strong></td> <td valign="top" width="115"><strong>Размер блока</strong></td> <td valign="top" width="147"><strong>Нижняя граница</strong></td> <td valign="top" width="274"><strong>Неиспользованный члены</strong></td> </tr> <tr> <td valign="top" width="93">1</td> <td valign="top" width="106"><strong><font color="#ff0000">6</font></strong>******</td> <td valign="top" width="115">8!/2! = 20160</td> <td valign="top" width="147">5*20160 = 100800</td> <td valign="top" width="274">12345<font color="#ff0000"><strong>6</strong></font>789</td> </tr> <tr> <td valign="top" width="93">2</td> <td valign="top" width="106">6<strong><font color="#ff0000">3</font></strong>*****</td> <td valign="top" width="115">7!/2! = 2520</td> <td valign="top" width="147">2*2520  =   5040</td> <td valign="top" width="274">12<strong><font color="#ff0000">3</font></strong>45789</td> </tr> <tr> <td valign="top" width="93">3</td> <td valign="top" width="106">63<strong><font color="#ff0000">8</font></strong>****</td> <td valign="top" width="115">6!/2! = 360</td> <td valign="top" width="147">5*360   =   1800</td> <td valign="top" width="274">12457<strong><font color="#ff0000">8</font></strong>9</td> </tr> <tr> <td valign="top" width="93">4</td> <td valign="top" width="106">638<strong><font color="#ff0000">1</font></strong>***</td> <td valign="top" width="115">5!/2! = 60</td> <td valign="top" width="147">0*60    =      0</td> <td valign="top" width="274"><strong><font color="#ff0000">1</font></strong>24579</td> </tr> <tr> <td valign="top" width="93">5</td> <td valign="top" width="106">6381<strong><font color="#ff0000">9</font></strong>**</td> <td valign="top" width="115">4!/2! = 12</td> <td valign="top" width="147">4*12    =     48</td> <td valign="top" width="274">2457<font color="#ff0000"><strong>9</strong></font></td> </tr> <tr> <td valign="top" width="93">6</td> <td valign="top" width="106">63819<strong><font color="#ff0000">4</font></strong>*</td> <td valign="top" width="115">3!/2! = 3</td> <td valign="top" width="147">1*3     =      3</td> <td valign="top" width="274">2<strong><font color="#ff0000">4</font></strong>57</td> </tr> <tr> <td valign="top" width="93">7</td> <td valign="top" width="106">638194<strong><font color="#ff0000">7</font></strong></td> <td valign="top" width="115">2!/2! = 1</td> <td valign="top" width="147">2*1     =      2</td> <td valign="top" width="274">25<strong><font color="#ff0000">7</font></strong></td> </tr> </tbody></table> <p align="justify">Номер размещения будет равен сумме нижних границ интервалов на каждой итерации: <br />100800+5040+1800+0+48+3+2 = 107693. Полученный номер был получен с тем расчетом, что изначально все размещения нумеровались с нуля. <br />Все вышесказанное можно реализовать таким образом:</p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">int</font> placement_amount(<font color="#0000ff">int</font> n, <font color="#0000ff">int</font> m) {</li> <li>  <font color="#0000ff">int</font> res = 1;</li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i = n; i >= n-m+1; --i) {</li> <li>    res *= i;</li> <li>  }</li> <li>  <font color="#0000ff">return</font> res;</li> <li>}</li> <li><font color="#0000ff">int</font> get_num_by_placement(<font color="#0000ff">const</font> vector<<font color="#0000ff">int</font>> &mas, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> m) {</li> <li>  vector<<font color="#0000ff">bool</font>> usd(n,<font color="#0000ff">false</font>);</li> <li>  <font color="#0000ff">int</font> res = 0;</li> <li>  <font color="#0000ff">int</font> _n = n-1, _m = m-1;</li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<mas.size();++i) {</li> <li>    <font color="#0000ff">int</font> amount = 0;</li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> j=0;j<n;++j) {</li> <li>      <font color="#0000ff">if</font> (!usd[j]) amount++;</li> <li>      <font color="#0000ff">if</font> (mas[i] == j) {</li> <li>        <font color="#0000ff">int</font> ampt = (amount - 1) * placement_amount(_n, _m);</li> <li>        res += (amount - 1) * placement_amount(_n, _m);</li> <li>        usd[j] = <font color="#0000ff">true</font>;</li> <li>      }</li> <li>    }</li> <li>    usd[mas[i]] = <font color="#0000ff">true</font>;</li> <li>    --_n; --_m;</li> <li>  }</li> <li>  <font color="#0000ff">return</font> res;</li> <li>}</li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> </font> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-57491227002240534802012-03-15T12:35:00.001+04:002012-03-15T12:35:44.840+04:00Генерация следующего и предыдущего размещения без повторений за O(N)<p align="justify"><font face="Courier New"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong>[Все темы по размещениям]</strong></a> <br /> <br /><strong><u>Теория</u></strong>: Окулов. Программирование в алгоритмах. 2004 <br /><strong><u>Практика</u></strong>: <a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>K4.Размещения.(dl.gsu.by)</strong></a> <br /> <br />На текущий момент мы умеем генерировать следующее размещение в лексикографическом порядке со <a href="http://cppalgo.blogspot.com/2012/03/onn-onlogn.html"><strong>сложностью O(N*N) и O(N*log(N))</strong></a>. Сегодня сделаем эту операцию с линейной сложностью. Для этого нужно будет вспомнить <a href="http://cppalgo.blogspot.com/2011/02/episode-2.html"><strong>алгоритм генерации следующей перестановки</strong></a> в лексикографическом порядке. Для удобства я буду пользовать STL’ным аналогом next_permutation. Итак начнем по порядку. <br /> <br />Пусть n = 9, m = 5. В качестве алфавита будем использовать цифры от 1 до 9. Рассмотрим текущее размещение <strong>P<sub>i</sub></strong> = {1,2,4,9,8}. Найдем следующее размещение <strong>P<sub>i+1</sub></strong> в лексикографическом порядке. <br />Поставим во взаимно-однозначное соответствие текущему размещению P<sub>i</sub> перестановку Perm<sub>i</sub>, префикс которой равен Pi, а постфикс формируется из оставшихся минимальных элементов алфавита, не использованных в P<sub>i</sub>.</font></p> <p align="justify"> <table border="0" cellspacing="0" cellpadding="2" width="790"><tbody> <tr> <td valign="top" width="133"><strong><font size="3"><font face="Courier New">Perm<sub>i</sub></font></font></strong></td> <td valign="top" width="133"><strong><font size="3"><font face="Courier New"><font color="#ff0000">12498</font><font color="#0000ff">3567</font></font></font></strong></td> <td valign="top" width="522"><font face="Courier New">Формируем перестановку Perm<sub>i</sub>.</font></td> </tr> <tr> <td valign="top" width="133"><strong><font size="3" face="Courier New"></font></strong></td> <td valign="top" width="133"><strong><font size="3"><font face="Courier New"><font color="#ff0000">12498</font><font color="#0000ff">7653</font></font></font></strong></td> <td valign="top" width="522"><font face="Courier New">Реверсируем хвост перестановки</font></td> </tr> <tr> <td valign="top" width="133"><strong><font size="3"><font face="Courier New">Perm<sub>i+1</sub></font></font></strong></td> <td valign="top" width="133"><strong><font size="3"><font face="Courier New"><font color="#ff0000">12534</font><font color="#0000ff">6789</font></font></font></strong></td> <td valign="top" width="522"><font face="Courier New">Генерируем следующую перестановку в лексикографическом порядке.</font></td> </tr> </tbody></table> <br /><font face="Courier New">Получив перестановку <strong>Perm<sub>i+1</sub></strong>, отбрасываем хвост и получаем следующее размещение <strong>P<sub>i+1</sub></strong>= {1,2,5,3,4}. <br />Если на каком-то этапе не получилось сгенерировать следующую перестановку, значит на текущем этапе обрабатывалось последнее размещение в лексикографическом порядке.</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">bool</font> next_placement(<font color="#0000ff">string</font> &perm, <font color="#0000ff">int</font> m) { </li> <li>  reverse(perm.begin()+m, perm.end()); </li> <li>  <font color="#0000ff">return</font> next_permutation(perm.begin(), perm.end()); </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New">Т.к. выполнение реверса хвоста и генерация следующей перестановки имеют сложность O(N), то и генерация следующего размещения так же будет иметь линейную сложность. <br /><strong><u>Полная реализация</u></strong>: <a href="http://www.everfall.com/paste/id.php?a7hqii2hyx92"><strong>здесь</strong></a> <br /> <br />Генерация предыдущего размещения выполняется таким же образом.</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">bool</font> prev_placement(<font color="#0000ff">string</font> &perm, <font color="#0000ff">int</font> m) { </li> <li>  reverse(perm.begin()+m, perm.end()); </li> <li>  <font color="#0000ff">return</font> prev_permutation(perm.begin(), perm.end()); </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New"><strong><u>Полная реализация:</u></strong> <a href="http://www.everfall.com/paste/id.php?fuobtwmk3f8b"><strong>здесь</strong></a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-47360100735209715652012-03-14T20:27:00.001+04:002012-03-14T20:34:41.341+04:00Генерация следующего размещения без повторений за O(N*N) и O(N*log(N))<p align="justify"><font face="Courier New"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong>[Все темы по размещениям]</strong></a> <br /> <br /><strong><u>Теория</u></strong>: Окулов. Программирование в алгоритмах. 2004 <br /><strong><u>Практика</u></strong>: <a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>K4.Размещения.(dl.gsu.by)</strong></a> <br /> <br />Пусть n = 9, а m = 6. Рассмотрим текущее размещение P<sub>i</sub> = {1,3,6,5,9,8}. Найдем следующее размещение P<sub>i+1</sub> в лексикографическом порядке. Алфавитом в данном случае будет являться набор цифр от 1 до 9. <br /> <br />Для начала разделим все элементы алфавита на две группы: <font color="#ff0000">те, что входят в текущее размещение P<sub>i</sub></font> и те, <font color="#0000ff">что нет(множество F - свободные члены)</font><font color="#000000">:</font></font> </p> <p align="center"><font face="Courier New"><strong><font size="3"><font color="#ff0000">136598</font><font color="#0000ff">247</font></font></strong></font></p> <p align="justify"><font color="#000000" face="Courier New">Будем последовательно перебирать элементы размещения P<sub>i</sub> справа налево. Если на каком-то этапе для текущего элемента размещения P<sub>i</sub>[j] можно найти элемент F[k] из свободных членов, который больше его, то заменяем P<sub>i</sub>[j] на F[k]. При этом F[k] должен быть минимально возможным. При этом может возникнуть две ситуации: <br />1) Это сделать удалось. При это нужно дополнить размещение так, чтобы ее размер стал равным m. Для этого на свободные места последовательно добавляем элементы множества F в порядке возрастания начиная с самого маленького. <br />2) Этого сделать не удалось. Текущий элемент P<sub>i</sub>[j] удаляем из текущего размещения и добавляем в множество F. Берем следующий элемент P<sub>i</sub>[j-1] и повторяем итерацию. Если же не удалось найти такой элемент, значит на текущей итерации мы работали с последним размещением в лексикографическом порядке. <br /> <br />Давайте получим размещение P<sub>i+1</sub> по вышеизложенным правилам:</font></p> <table border="0" cellspacing="0" cellpadding="2" width="814"><tbody> <tr> <td width="78"><font face="Courier New"><strong><font size="3">P<sub>i   </sub>=</font></strong></font></td> <td width="96"><font face="Courier New"><font color="#0000ff"><strong><font color="#ff0000" size="3">136598</font></strong><strong><font size="3">247</font></strong></font></font></td> <td width="639"> <p><font face="Courier New">Нет свободного элемента больше <strong><font color="#ff0000">8</font></strong></font></p> </td> </tr> <tr> <td width="78"><font face="Courier New"></font></td> <td width="96"><strong><font size="3" face="Courier New"><font color="#ff0000">13659</font><font color="#0000ff">2478</font></font></strong></td> <td width="639"> <p><font face="Courier New">Нет свободного элемента больше <strong><font color="#ff0000">9</font></strong></font></p> </td> </tr> <tr> <td width="78"><font face="Courier New"></font></td> <td width="96"><strong><font size="3" face="Courier New"><font color="#ff0000">136<font style="background-color: #ffff00">5</font></font><font color="#0000ff">24<font style="background-color: #ffff00">7</font>89</font></font></strong></td> <td width="639"> <p><font face="Courier New">Есть 3 свободных элемента больше <strong><font color="#ff0000">5</font></strong>: <strong><font color="#0000ff">7,8,9</font></strong>. Выбираем <strong><font color="#0000ff">7</font></strong> и меняем их местами</font></p> </td> </tr> <tr> <td width="78"><font face="Courier New"></font></td> <td width="96"><font face="Courier New"><font size="3"><strong><font color="#ff0000">1367</font><font color="#0000ff">24589</font></strong></font></font></td> <td width="639"> <p><font face="Courier New">Первые 4 элемент размещения <strong><font size="3">P<sub>i+1</sub></font></strong> определены</font></p> </td> </tr> <tr> <td valign="top" width="78"><font face="Courier New"><font size="3"><strong>P<sub>i+1 </sub>=</strong></font></font></td> <td valign="top" width="96"><font size="3" face="Courier New"><strong><font color="#ff0000">136724</font><font color="#0000ff">589</font></strong></font></td> <td width="639"><font face="Courier New">Дополняем префикс размещения <font size="3">P<sub>i+1</sub></font><strong> </strong></font></td> </tr> </tbody></table> <p><font face="Courier New">Данный подход можно реализовать со сложностью <strong><font size="3">O(N*N)</font></strong>:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">string</font> letters = <font color="#a31515">"1234567"</font>; </li> <li><font color="#0000ff">bool</font> next_placement(<font color="#0000ff">string</font> &cur, vector<<font color="#0000ff">bool</font>> &usd, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> m) { </li> <li>  <font color="#0000ff">int</font> beg = -1; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=m-1;i>=0;--i) { </li> <li>    <font color="#0000ff">if</font> (beg != -1) <font color="#0000ff">break</font>; </li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> j=cur[i] - letters[0] + 1; j < n; ++j) { </li> <li>      <font color="#0000ff">if</font> (!usd[j]) { </li> <li>        usd[j] = <font color="#0000ff">true</font>; </li> <li>        usd[cur[i] - letters[0]] = <font color="#0000ff">false</font>; </li> <li>        cur[i] = letters[j]; </li> <li>        beg = i; </li> <li>        <font color="#0000ff">break</font>; </li> <li>      } </li> <li>    } </li> <li>    <font color="#0000ff">if</font> (beg == -1) </li> <li>      usd[cur[i] - letters[0]] = <font color="#0000ff">false</font>; </li> <li>  } </li> <li>  <font color="#0000ff">if</font> (beg != -1) { </li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=beg+1, j = 0; i<m && j<n;++j) { </li> <li>      <font color="#0000ff">if</font> (!usd[j]) { </li> <li>        usd[j] = <font color="#0000ff">true</font>; </li> <li>        cur[i++] = letters[j]; </li> <li>      } </li> <li>    } </li> <li>    <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>  } </li> <li>  <font color="#0000ff">else</font> </li> <li>    <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New">Рассмотрим параметры, передаваемые в функцию next_placement: <br />1. cur – текущее размещение. <br />2. usd – массив меток. Если usd[i] == false, значит i-ый элемент алфавита является свободным членом. <br />Т.к. текущее размещение cur передается по ссылке, то после выполнения функции оно заменится на следующее размещение в лексикографическом порядке. <br /> <br /><strong><u>Полная реализация</u></strong>: <a href="http://www.everfall.com/paste/id.php?23s0ggmt038g"><strong><u>здесь</u></strong></a> <br /> <br />Немного подумав, можно смело заменить массив меток на множество(set) свободных членов, улучшив асимптотику до <strong>O(N*log(N))</strong>:</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">bool</font> next_placement(<font color="#0000ff">string</font> &cur, <font color="#0000ff">set</font><<font color="#0000ff">char</font>> &vac, <font color="#0000ff">int</font> n, <font color="#0000ff">int</font> m) { </li> <li>  <font color="#0000ff">set</font><<font color="#0000ff">char</font>>::iterator it; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=cur.size()-1;i>=0;--i) { </li> <li>    it = vac.lower_bound(cur[i]); </li> <li>    <font color="#0000ff">if</font> (it != vac.end()) { </li> <li>      <font color="#0000ff">char</font> tmp = cur[i]; </li> <li>      cur[i] = *it; </li> <li>      vac.erase(it); </li> <li>      vac.insert(tmp); </li> <li>      <font color="#0000ff">for</font> (<font color="#0000ff">int</font> pos = i+1; pos < m; ++pos) { </li> <li>        cur[pos] = *vac.begin(); </li> <li>        vac.erase(vac.begin()); </li> <li>      } </li> <li>      <font color="#0000ff">return</font> <font color="#0000ff">true</font>; </li> <li>    } </li> <li>    vac.insert(cur[i]); </li> <li>  } </li> <li>  <font color="#0000ff">return</font> <font color="#0000ff">false</font>; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New"><strong><u>Полная реализация</u></strong>: <a href="http://www.everfall.com/paste/id.php?sv027zqdj9ph"><strong><u>здесь</u></strong></a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-51016346144153494552012-03-12T20:40:00.001+04:002012-03-12T20:55:20.630+04:00Генерация всех размещений без повторений рекурсивным способом<p align="justify"><font face="Courier New"><a href="http://cppalgo.blogspot.com/2012/03/placement.html"><strong>[Все темы по размещениям]</strong></a> <br /> <br /><strong><u>Теория</u></strong>: Окулов. Программирование в алгоритмах. 2004 <br /><strong><u>Практика</u>: </strong><a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>K4.Размещения.(dl.gsu.by)</strong></a> <br /> <br />Представим, что нужно рассадить N гостей на M мест, при этом может получиться такая ситуация, что некоторые гости останутся стоять. Занумеруем всех гостей числами от 1 до N. А теперь давайте попробуем перечислить все возможные посадки. Пусть N = 4, а M = 3. Получаем:</font><font face="Courier New"> </font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>123 </li> <li>124 </li> <li>132 </li> <li>134 </li> <li>142 </li> <li>143 </li> <li>213 </li> <li>214 </li> <li>231 </li> <li>234 </li> <li>241 </li> <li>243 </li> <li>312 </li> <li>314 </li> <li>321 </li> <li>324 </li> <li>341 </li> <li>342 </li> <li>412 </li> <li>413 </li> <li>421 </li> <li>423 </li> <li>431 </li> <li>432 </li> </ol> </font></code> <p align="justify"><font face="Courier New">Чтобы убедиться в том, что ни одна комбинация не была пропущена, найдем общее количество размещений по формуле A(M,N) = N! / (N-M)! = 4! / 1! = 24. Можно двигаться дальше. <br />Что касается самого принципа генерации, то он полностью совпадает с принципом <a href="http://cppalgo.blogspot.com/2011/02/episode-1.html"><strong><u>генерации перестановок без повторений</u></strong></a>. Тем более, что если N = M, то будет происходить генерация всех перестановок без повторения.</font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">int</font> n,m; </li> <li><font color="#0000ff">string</font> letters = <font color="#a31515">"1234567"</font>; </li> <li>vector<<font color="#0000ff">bool</font>> usd; </li> <li><font color="#0000ff">string</font> res; </li> <li></li> <li><font color="#0000ff">void</font> placement_lex(<font color="#0000ff">int</font> pos) { </li> <li>  <font color="#0000ff">if</font> (pos == m) { </li> <li>    printf(<font color="#a31515">"%s\n"</font>, res.c_str()); </li> <li>    <font color="#0000ff">return</font>; </li> <li>  } </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<n;++i) { </li> <li>    <font color="#0000ff">if</font> (!usd[i]) { </li> <li>      usd[i] = <font color="#0000ff">true</font>; </li> <li>      res[pos] = letters[i]; </li> <li>      placement_lex(pos+1); </li> <li>      res[pos] = <font color="#a31515">' '</font>; <font color="#008000">// debug only</font> </li> <li>      usd[i] = <font color="#0000ff">false</font>; </li> <li>    } </li> <li>  } </li> <li>} </li> <li><font color="#0000ff">int</font> main() { </li> <li>    ... </li> <li>  usd.resize(n); </li> <li>  res.resize(m,<font color="#a31515">' '</font>); </li> <li>  placement_lex(0); </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New"><strong><u>Решение</u></strong>: <a href="http://www.everfall.com/paste/id.php?iw6fa691l6lo"><strong><u>здесь</u></strong></a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com1tag:blogger.com,1999:blog-9149260308162775442.post-12696855790286067182012-03-12T20:01:00.001+04:002012-03-25T23:37:05.028+04:00Размещения (placements)<p> <br /><font face="Courier New"><font size="3"><strong><font color="#ff0000">Размещения без повторений</font></strong> <br /></font><font size="3"><font size="2">         <strong><u>Вопрос</u></strong>: “Сколькими способами можно разместить N гостей по M местам?” (N >= M) <br />         <strong><u>Правило</u></strong>: Порядок имеет значение, т.е. картежи {1,4,2} и {2,4,1} являются различными.</font> <br /><font size="2"><strong>         <a href="http://www.everfall.com/paste/id.php?2akz5395zo9w"><u>Количество</u></a></strong>: A(M,N) = N * (N-1) * (N-2) * (N - M + 1) = N! / (N - M)! </font> <br /><strong>1. Генерация всех размещений без повторений <br /></strong></font><font size="2"><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/blog-post.html"><strong>1.1. Рекурсивная генерация в лексикографическом порядке</strong></a> <br /><strong>          <u>Практика</u>: </strong><a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>[K4.Размещения(dl.gsu.by)]</strong></a> <br /><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/onn-onlogn.html"><strong>1.2. Генерация следующего размещения в лексикографическом порядке(без перестановок) O(N*N)</strong></a><strong> <br />          <u>Практика</u>: </strong><a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>[K4.Размещения(dl.gsu.by)]</strong></a> <br /><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/onn-onlogn.html"><strong>1.3. Генерация следующего размещения в лексикографическом порядке(без перестановок) O(logN*N)</strong></a><strong> <br />          <u>Практика</u>: </strong><a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>[K4.Размещения(dl.gsu.by)]</strong></a> <br /><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/on.html"><strong>1.4. Генерация следующего размещения в лексикографическом порядке(с перестановками) O(N)</strong></a> <br /><strong>          <u>Практика</u>: </strong><a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>[K4.Размещения(dl.gsu.by)]</strong></a> <br /><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/on.html"><strong>1.5. Генерация предыдущего размещения в лексикографическом порядке                  O(N)</strong></a><strong> <br />          <u>Практика</u>: </strong><a href="http://dl.gsu.by/task.jsp?nid=40104&cid=15"><strong>[K4.Размещения(dl.gsu.by)]</strong></a> <br /></font></font><font face="Courier New"><font size="3"><strong><a href="http://cppalgo.blogspot.com/2012/03/onn_16.html">2. Генерация размещения по номеру L (задаются значения M и N)          O(N*N)</a> <br /></strong><font size="2">          <strong><u>Практика</u>: <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3784">[3784. Генерация размещений]</a></strong></font> <br /><strong><a href="http://cppalgo.blogspot.com/2012/03/onn.html">3. Получения номера по размещению (задаются значения M и N)            O(N*N)</a>  <br /></strong></font><strong>          <u>Практика</u>: </strong><a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=192"><strong>[192. По размещению]</strong></a> <br /> <br /></font></p> <p><font color="#ff0000" size="3" face="Courier New"><strong>Размещения с повторениями <br /></strong><font color="#000000" size="2">         <strong><u>Вопрос</u></strong>: “Сколько различных букетов можно собрать из K цветков, используя N видов цветов” <br />         <strong><u>Правило</u></strong>: Порядок имеет значение, т.е. картежи {1,1,5} и {1,5,1} являются различными. <br />         <strong><a href="http://www.everfall.com/paste/id.php?j95ftf2ttlbo"><u>Количество</u></a>:</strong> A(K,N) = <font size="3">N<sup>K</sup></font>, где N - мощность алфавита, K - длина последовательности <br /><font size="3"><strong>4. Генерация всех размещений без повторений. <br /></strong><font size="2"><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/blog-post_20.html"><strong>4.1. Рекурсивная генерация в лексикографическом порядке</strong></a> <br /><strong>          <u>Практика</u>: </strong><a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=82#1"><strong>[82. Все строки длины n из k различных символов]</strong></a> <br /><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/blog-post_22.html"><strong>4.2. Генерация следующего размещения в лексикографическом порядке</strong></a> <br /><strong>          <u>Практика</u>: </strong><a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=82#1"><strong>[82. Все строки длины n из k различных символов]</strong></a> <br /><strong>     </strong><a href="http://cppalgo.blogspot.com/2012/03/blog-post_22.html"><strong>4.3. Генерация предыдущего размещения в лексикографическом порядке</strong></a><strong> <br />          <u>Практика</u>: </strong><a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=211&chapterid=83#1"><strong>[83. Все строки длины n из k различных символов в обратном порядке]</strong></a></font> <br /><strong><a href="http://cppalgo.blogspot.com/2012/03/blog-post_23.html">5. Генерация размещения по номеру L (задаются значения K и N)</a></strong> <br /><strong><a href="http://cppalgo.blogspot.com/2012/03/blog-post_9437.html">6. Получение номера по размещению (задаются значения K и N)</a> <br /><a href="http://cppalgo.blogspot.com/2012/03/blog-post_25.html">7. Расстановка знаков в арифметическом выражении</a></strong></font></font></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-83584554366848939862012-02-10T18:56:00.001+04:002012-02-10T18:56:15.665+04:00задача Футурама (3298 на informatics.mccme.ru)<p align="justify"><font face="Courier New"><a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3298"><strong>Условие</strong></a> <br />Эта задача показалась мне довольно интересной. Тем более, что она имеет схожие черты с другой очень хорошей задачей <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=&chapterid=1231"><strong>D++</strong></a>. <br /> <br />Итак, суть сводится к тому, что нужно упорядочить массив с учетом того, что последние два элемента гарантированно находятся на своих позициях. Элементы, находящиеся на позициях i и j запрещается менять местами, если ранее уже совершались обмены i-ого и j-ого элементов. <br />Из условия нам дают понять как можно обменять два элемента местами, используя два последних элемента. Пусть нужно обменять элементы 3 и 4, находящихся на позициях i и j: <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; display: block; float: none; margin-left: auto; border-top: 0px; margin-right: auto; border-right: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-C6ETHgA5pyc/TzUisjNEO_I/AAAAAAAAB6A/IINA7VMTyow/s510/simple_swap.png" /></font></p> <p align="justify"><font face="Courier New">Теперь нужно вспомнить, что исходный набор чисел является перестановкой. Это позволяет разложить имеющуюся перестановку на <a href="http://cppalgo.blogspot.com/2011/02/blog-post.html"><strong>циклы</strong></a> и уже в дальнейшем работать с каждым циклом отдельно. <br />Понятно, что если упорядочить элементы в каждом цикле, то исходная перестановка станет единичной, т.е. упорядоченной. <br />В представленном решении не нужно помнить о запрещенных позициях для обменов, т.к. они все будут осуществляться через последние два элемента. Для любого цикла перестановки справедлив один из случаев: <br />1) Длина цикла равна 1. Понятно, элемент цикла находится на “нужном” месте в перестановке и ничего делать не нужно <br />2) Длина цикла равна 2. В данном случае элементы цикла можно обменять местами по правилу изложенному выше <br />3) Длина цикла больше 2. Это самый сложный случай. Рассмотрим перестановку A = {5,6,4,1,3,2,7,8}: <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; display: block; float: none; margin-left: auto; border-top: 0px; margin-right: auto; border-right: 0px; padding-top: 0px" border="0" src="https://lh3.googleusercontent.com/-hQ5bTn6ewZY/TzUpn_xHBuI/AAAAAAAAB6M/uJoMNYEZtwM/s573/circle.png" /></font></p> <p align="justify"><font face="Courier New">Один из циклов перестановки С = 1-5-3-4-1. Поставим на свои элементы цикла, отличные от двух последних(1 и 4), т.е. 5 и 3. Это можно сделать с помощью промежуточных обменов с предпоследним элементом перестановки: <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; display: block; float: none; margin-left: auto; border-top: 0px; margin-right: auto; border-right: 0px; padding-top: 0px" border="0" src="https://lh3.googleusercontent.com/-89ekcG54h-I/TzUqzKlnwKI/AAAAAAAAB6Y/zKIdcskjhRc/s573/circle_sort.png" /></font></p> <p><font face="Courier New">Получилась перестановка B = {7,6,3,1,5,2,4,8}. Теперь немного отвлечемся и рассмотрим перестановку <br /> A’={4,6,3,1,5,2,7,8}. Она имеет цикл С’ = 1-4, в то время, как элементы 3 и 5 находятся на “своих” местах. Для упорядочивания цикла C’ можно воспользоваться п.2) <br />Перестановка B получается из перестановки A’ после первого же обмена. Поэтому чтобы закончить п.3) необходимо выполнить оставшиеся 3 обмена, чтобы обменять в перестановке A’ элементы 1 и 4: <br /><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; display: block; float: none; margin-left: auto; border-top: 0px; margin-right: auto; border-right: 0px; padding-top: 0px" border="0" src="https://lh3.googleusercontent.com/-K3JXzhoGuxg/TzUugZMXoEI/AAAAAAAAB6k/qyPhz2avSv4/s574/circle_sort_fin.png" /></font></p> <p><font face="Courier New">После сортировки каждого цикла последние два элемента меняются местами, поэтому если количество циклов является нечетным, то на последней итерации необходимо их поменять местами. <br /> <br /><a href="http://www.everfall.com/paste/id.php?z5ullzmbtqfb"><strong><u><font size="3">Решение</font></u></strong></a></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-24001525441421674462012-01-31T20:54:00.001+04:002012-02-10T19:49:22.978+04:00Contest list<p><font face="Courier New">В данном посте буду формировать список прорешенных контестов. <br /> <br />Div1: <br /><strong><font size="3">1[+]. Московская командная олимпиада 2003 </font></strong> <br />[15Jan12 - 17Jan12]     <a href="http://informatics.mccme.ru/moodle/mod/statements/view.php?id=942"><strong>[Условие]</strong></a> <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?k2rccxbfzeox"><strong>A. Перегоны</strong></a>                    (алгоритм Флойда) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?4jdakceqcoa1"><strong>$B. Сломанный калькулятор</strong></a><strong>  </strong>     (Теория чисел) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?64i8r2ybukll"><strong>C. Валютные махинации</strong></a>          (ДП-1) (* цифра после ДП означает уровень сложности: 1 – легкая) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?i0j7u6j9u1za"><strong>D. Двухтуровая олимпиада</strong></a>       (Моделирование) <br />    <strong></strong><a href="http://www.everfall.com/paste/id.php?hxobi0wrtdbs"><strong>E. Черно-белые палиндромы</strong></a><strong> </strong>     (Строки, Хеширование) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?z9tymhwrkfzc"><strong>F. Луч света в темном царстве</strong></a>  (Моделирование, Матрицы) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?8rid1su4c9ew"><strong>G. Распаковка строчки</strong></a>          (Строки) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?dlcfn9tmhml4"><strong>*H. Дремучий лес</strong></a>                (Геометрия) <br /><strong><font size="3">2[+]. Московская командная олимпиада 2004 <br /></font></strong>[31Dec11-03Jan2012]     <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=941&chapterid=1228#1"><strong>[Условие]</strong></a> <br />  <strong>  </strong><a href="http://www.everfall.com/paste/id.php?e0pklyqpjoiy"><strong>A. Москва – сортировочная</strong></a>  (Поощрительная) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?mr88ykshpouu"><strong>B. Кафе</strong></a>                    (ДП-2) <br />  <strong>  </strong><a href="http://www.everfall.com/paste/id.php?hupxu3erqpa1"><strong>C. Euro-English</strong></a>            (Строки - муторные) <br /><strong>  </strong><a href="http://www.everfall.com/paste/id.php?y7pg93qleli6"><strong>$$D. D++</strong></a>                     (Моделирование. Цикл перестановки) <br />   <a href="http://www.everfall.com/paste/id.php?ksnxhxxz8h72"><strong>$E. Скобки</strong></a>                  (ДП-2) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?6i9ohgt3e0bd"><strong>F. Двоякие числа</strong></a>           (Поощрительная. Теория чисел) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?q03agmjq9cng"><strong>*G. OOO</strong></a>                     (Геометрия – 25 случаев) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?npaip0sw2a02"><strong>H. Калах</strong></a>                   (Моделирование) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?m3tzdldzysm8"><strong>I. Сортировка масс</strong></a>         (Сортировка. Тип данных) <br /><font size="3"><strong>3[+]. Московская командная олимпиада 2005 </strong></font> <br />[05Jan12 - 11Jan12]     <a href="http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=201&chapterid=26#1"><strong>[Условие]</strong></a> <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?l0o9vrdcm30g"><strong>A. Результаты олимпиады</strong></a>      (Моделирование) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?9gjb50hm4ajd"><strong>B. Сокращение дроби</strong></a>          (GCD) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?356fdjbxczvt"><strong>C. Современники</strong></a>              (Сортировка. Моделирование) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?6n9vdiv1lpzy"><strong>$D. Тройки чисел</strong></a>              (Теория чисел) <br />  <strong> </strong><a href="http://www.everfall.com/paste/id.php?bcx06kgqu5zp"><strong>$E. T2005(Sort)</strong></a>  <a href="http://www.everfall.com/paste/id.php?xtt5a17xpgff"><strong>T2005(Бор)</strong></a>   (Сортировка. Бинарный поиск / Бор) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?z4bb66p1q498"><strong>F. Роботы</strong></a>                    (Теория графов. Моделирование. Поиск в ширину. Битовая маска) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?pn3vutpsze09"><strong>$G. Монетки</strong></a>                   (Перебор. 2^30 > 3^15) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?alnuwqeiimqh"><strong>H. Сверим часы</strong></a>               (Моделирование. Время) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?fgclcv5358dl"><strong>*I. Разрезанный прямоугольник</strong></a> (Геометрия) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?7jyv8sqday3s"><strong>$J. Количество треугольников</strong></a>  (Арифметическая прогрессия) <br /><strong><font size="3">4[+]. RROI–2012(Региональный этап всероссийской олимпиады школьников 2011-2012)  <br /></font></strong>[27Jan12 - 31Jan12]     <a href="http://yeputons.net/tsweb/stats/12roi_reg.pdf"><strong>[Условие]</strong></a>                                          <a href="http://informatics.mccme.ru/moodle/mod/resource/view.php?id=4335"><strong>[Разбор от М.Гуровица]</strong></a> <br />    <a href="http://www.everfall.com/paste/id.php?2o6lw4kdcdz8"><strong>A. Цапли</strong></a>                 (Поощрительная) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?vrb32e25nxwh"><strong>B. Круглый стол</strong></a>          (Моделирование) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?cbuwqel6c3td"><strong>С. Поврежденный XML</strong></a>      (Строки, Полный перебор)  <br /><strong>  </strong><a href="http://www.everfall.com/paste/id.php?rywvyppbraqf"><strong>$*D. Игра с числами</strong></a><strong>     </strong>   (Теория игр) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?qlk6ouzyjxy5"><strong>E. Кондиционер</strong></a>           (Поощрительная) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?jsm0qoyv0fjr"><strong>F. Космический кегельбан</strong></a> (Геометрия) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?qqzs7k2998t6"><strong>G. Abracadabra</strong></a>           (Бор, Хеширование)</font><font face="Courier New"> <br /> <br /> <br />Div2(исходники и разборы только самых интересных задач): <br />1[+]. Московская индивидуальная олимпиада 7-9 класс (2006) [28Dec2011] <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?qzwctp1ewple"><strong>С. Кинотеатр</strong></a> <a href="http://www.everfall.com/paste/id.php?0h2zy1gaesjg"><strong>[второе решение]</strong></a>  (Мальчики/Девочки) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?8saa5od4ezo6"><strong>E. Метро</strong></a>                       (Поиск в ширину)  <br />2[+]. Московская индивидуальная олимпиада 7-9 класс (2007) [28Dec2011] <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?93l6r3g37l07"><strong>D. Кассы</strong></a>    (Время) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?vk4hxuhntdzm"><strong>E. Словарь</strong></a>  (ДП-2) <br />3[+]. Московская индивидуальная олимпиада 7-9 класс (2008) [19Jan2012] <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?s0iscoc0qh5t"><strong>A. Автобусы</strong></a> (Моделирование. Мальчики/Девочки) <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?ggva8am5g9c6"><strong>D. Реклама</strong></a>  (Быстрая сортировка) <br />4[+]. Московская индивидуальная олимпиада 7-9 класс (2009) [26Dec2011] <br /><strong>    </strong><a href="http://www.everfall.com/paste/id.php?jbcgavrhn3ss"><strong>D. Изобретательный Петя</strong></a> (Строки. Хеширование)  <br />5[-]. Московская индивидуальная олимпиада 7-9 класс (2010) <br />6[+]. Московская индивидуальная олимпиада 6-9 класс (2011) [04Feb2012-10Feb2012] <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?w7m9p54p56om"><strong>*D. Поход</strong></a>      (ДП-2) <br /><strong>   </strong><a href="http://www.everfall.com/paste/id.php?ds3paum0yhuj"><strong>$E. Футурама</strong></a>   (Цикл перестановки) + <a href="http://cppalgo.blogspot.com/2012/02/3298-informaticsmccmeru.html"><strong>[пост]</strong></a> <br /> <br /></font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com2tag:blogger.com,1999:blog-9149260308162775442.post-75561294468555946932011-12-21T22:32:00.001+04:002011-12-21T23:20:06.433+04:00Tim Sort<p align="justify"><a href="http://cppalgo.blogspot.com/2010/09/blog-post_05.html"><font size="3" face="Courier New"><strong>[Все сортировки]</strong></font></a><font size="3" face="Courier New"><strong> <br /> <br /><u>Теория</u>: </strong></font><a href="http://habrahabr.ru/blogs/algorithm/133303/"><font size="3" face="Courier New"><strong><u>habrahabr.ru</u></strong></font></a><font size="3" face="Courier New"><strong>, </strong></font><a href="http://code.google.com/p/timsort/source/browse/trunk/timSort.c?spec=svn17&r=17"><font size="3" face="Courier New"><strong><u>код реальных мужиков на С</u></strong></font></a><font size="3" face="Courier New"><strong> (</strong></font><a href="http://www.everfall.com/paste/id.php?3ovn5ricu4l0"><font size="3" face="Courier New"><strong><u>зеркало</u></strong></font></a><font size="3" face="Courier New"><strong>) <br /> <br /><u>Практика</u>: </strong></font><a href="http://informatics.mccme.ru/moodle/mod/statements/view.php?id=598"><font size="3" face="Courier New"><strong><u>informatics.mccme.ru</u></strong></font></a><font face="Courier New"><font size="3"><strong> <br /> <br /><u>Немного размышлений</u>: <br /></strong></font>1) Не так давно общественность была взбудоражена малоизвестной сортировкой Tim Sort, которая творит чудеса. Поэтому возникло желание попробовать сделать ее реализацию. Когда разбирался в описании, представленном на хабре и в wikipedia, как в русской, так и в английской, возникли вопросы, на которые я не смог найти ответы. Больше всего вызывала вопросов та часть, в которой происходит эффективное слияние подмассивов, примерно равной длины. Т.к. я писал сортировку для случайного набора данных, поэтому хотелось избежать непоняток с волшебными длинами X,Y и Z, а именно просто сливать два последних подмассива, если они имеют одинаковую длину. Как показала практика в оригинальном алгоритме преследовалась та же идея. <br /></font></p> <p align="justify"><font face="Courier New">Разбираясь в реализации на С(см. теория), было выведено правило грамотного слияния подмассивов с поддержанием баланса длин. Пусть X,Y,Z  - длины верхних трех интервалов, которые лежат в стеке. Причем X – это последний элемент стека. <br /></font><font face="Courier New"><strong><u>Правило следующее:</u> <br /></strong>1. Повторяем пока выражение (Z > X + Y && Y > X) не станет истинным <br />2. Если количество элементов в стеке не меньше 3 и Z <= X + Y – сливаем Y c min(X,Z). <br />   Иначе Если Y<=X – сливаем X c Y <br />3. Возвращаемся в п.1. <br /> <br />В wikipedia и на habr’e написано другое правило, в котором X и Z поменены местами, и по которому ничего путного сделать у меня не получилось. <br /> <br />2) В оригинальной идее предполагалось, что во временный массив помещается меньший из сливаемых подмассивов. При этом, если это левый подмассив, то формирование результирующего массива идет слева направо + используется бинарный поиск по не убыванию. В противном случае, когда правый подмассив имеет размер меньше чем левый, ответ формируется справа налево + используется бинарный поиск по не возрастанию. Скажу честно, мне было лень замачиваться на такие вещи, поэтому в приведенной реализации всегда копируется левый подмассив. <br /> <br />3) Для меня осталась загадкой, откуда у автора алгоритма Тима Петерсона такая любовь к сортировке вставками, которая требует в худшем случае n(n-1)/2 обменов. Хотя конечно, для худшего случая, когда массив упорядочен в обратном порядке, стоят нужные механизмы, которые реверснут массив за n/2 обменов, но все равно вопрос для меня остался открытым. В этом плане мне больше импонирует сортировка выбором, которая требует не более n обменов, которая и была приведена в реализации. <br /> <br /><u><strong><font size="3">Реализация:</font></strong></u> <br /></font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#0000ff">struct</font> segment { </li> <li>  <font color="#0000ff">int</font> beg; <font color="#008000">// индекс первого элемента</font> </li> <li>  <font color="#0000ff">int</font> len; <font color="#008000">// длина интервала</font> </li> <li>  segment(){} </li> <li>  segment(<font color="#0000ff">int</font> b, <font color="#0000ff">int</font> l) : beg(b), len(l){} </li> <li>}; </li> <li><font color="#008000">// ответ должен быть в диапазоне (32,64]</font> </li> <li>inline <font color="#0000ff">int</font> get_min_size(<font color="#0000ff">int</font> n) { </li> <li>  <font color="#0000ff">int</font> r = 0; </li> <li>  <font color="#0000ff">while</font> (n >= 64) { </li> <li>    n >>= 1; </li> <li>    r |= n &1; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> n + r; </li> <li>} </li> <li><font color="#008000">// Да простит меня Тим Петерсон, но вместо сортировки вставками</font> </li> <li><font color="#008000">// я использую сортировку выбором</font> </li> <li><font color="#0000ff">void</font> selection_sort(vector<<font color="#0000ff">int</font>> &mas, <font color="#0000ff">int</font> beg, <font color="#0000ff">int</font> last) { </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=beg; i<last;++i) { </li> <li>    <font color="#0000ff">int</font> min_pos = i; </li> <li>    <font color="#0000ff">for</font> (<font color="#0000ff">int</font> j=i+1; j<last; ++j) { </li> <li>      <font color="#0000ff">if</font> (mas[j] < mas[min_pos]) </li> <li>        min_pos = j; </li> <li>    } </li> <li>    swap(mas[i],mas[min_pos]); </li> <li>  } </li> <li>} </li> <li><font color="#0000ff">const</font> <font color="#0000ff">int</font> dx = 1, dy = 2, dz = 3; </li> <li><font color="#0000ff">void</font> merge(vector<<font color="#0000ff">int</font>> &mas, vector<segment> &seg, <font color="#0000ff">bool</font> isXY, vector<<font color="#0000ff">int</font>> &tmp) { </li> <li>  segment f = seg[seg.size() - dy]; </li> <li>  segment s = isXY ? seg[seg.size() - dx] : seg[seg.size() - dz]; </li> <li>  <font color="#0000ff">if</font> (f.beg > s.beg) swap(f,s); </li> <li>  <font color="#0000ff">int</font> posF = 0, posS = s.beg, pos = f.beg-1; </li> <li>  <font color="#0000ff">int</font> lstF = f.len, lstS = s.beg + s.len; </li> <li>  copy(mas.begin() + f.beg + posF, mas.begin() + f.beg + lstF, tmp.begin()); </li> <li>  <font color="#0000ff">int</font> fAmount = 0, sAmount = 0; </li> <li>  <font color="#0000ff">while</font> (posF < lstF && posS < lstS) { </li> <li>    <font color="#0000ff">if</font> (tmp[posF] < mas[posS]) { </li> <li>      mas[++pos] = tmp[posF++]; </li> <li>      ++fAmount; sAmount=0; </li> <li>      <font color="#0000ff">if</font> (fAmount == 7) { </li> <li>        vector<<font color="#0000ff">int</font>>::iterator it = upper_bound(tmp.begin() + posF, tmp.begin() + lstF, mas[posS]); </li> <li>        copy(tmp.begin() + posF, it, mas.begin() + pos + 1); </li> <li>        pos += it - (tmp.begin() + posF); </li> <li>        posF += it - (tmp.begin() + posF); </li> <li>      } </li> <li>    } </li> <li>    <font color="#0000ff">else</font> { </li> <li>      mas[++pos] = mas[posS++]; </li> <li>      fAmount=0; ++sAmount; </li> <li>      <font color="#0000ff">if</font> (sAmount == 7) { </li> <li>        vector<<font color="#0000ff">int</font>>::iterator it = upper_bound(mas.begin() + posS, mas.begin() + lstS, tmp[posF]); </li> <li>        copy(mas.begin() + posS, it, mas.begin() + pos + 1); </li> <li>        pos += it - (mas.begin() + posS); </li> <li>        posS += it - (mas.begin() + posS); </li> <li>      } </li> <li>    } </li> <li>  } </li> <li>  copy(tmp.begin() + posF, tmp.begin() + lstF, mas.begin() + pos + 1); </li> <li>} </li> <li><font color="#0000ff">void</font> try_merge(vector<<font color="#0000ff">int</font>> &mas, vector<segment> &seg, vector<<font color="#0000ff">int</font>> &tmp, <font color="#0000ff">bool</font> is_merge = <font color="#0000ff">false</font>) { </li> <li>  <font color="#0000ff">while</font> (seg.size() > 1) { </li> <li>    <font color="#0000ff">int</font> x = seg[seg.size() - dx].len; </li> <li>    <font color="#0000ff">int</font> y = seg.size() < 2 ? 0 : seg[seg.size() - dy].len; </li> <li>    <font color="#0000ff">int</font> z = seg.size() < 3 ? 0 : seg[seg.size() - dz].len; </li> <li>    <font color="#0000ff">if</font> (seg.size() >= 3 && z <= x + y) { </li> <li>      <font color="#0000ff">if</font> (z < x) { </li> <li>        merge(mas,seg,<font color="#0000ff">false</font>,tmp); </li> <li>        seg[seg.size() - dz].len += seg[seg.size() - dy].len; </li> <li>        seg[seg.size()- dy] = seg[seg.size()- dx]; </li> <li>        <font color="#0000ff">goto</font> POP_BACK; </li> <li>      } </li> <li>      <font color="#0000ff">else</font> { </li> <li>        merge(mas,seg,<font color="#0000ff">true</font>,tmp);      </li> <li>        seg[seg.size() - dy].len += seg[seg.size() - dx].len; </li> <li>        <font color="#0000ff">goto</font> POP_BACK; </li> <li>      } </li> <li>    } </li> <li>    <font color="#0000ff">else</font> <font color="#0000ff">if</font> (is_merge || y <= x) { </li> <li>      merge(mas,seg,<font color="#0000ff">true</font>,tmp); </li> <li>      seg[seg.size() - dy].len += seg[seg.size() - dx].len; </li> <li>      <font color="#0000ff">goto</font> POP_BACK; </li> <li>    } </li> <li>    <font color="#0000ff">else</font> </li> <li>      <font color="#0000ff">break</font>; </li> <li>POP_BACK: seg.pop_back(); </li> <li>  } </li> <li>} </li> <li><font color="#0000ff">void</font> tim_sort(vector<<font color="#0000ff">int</font>> &mas) { </li> <li>  <font color="#0000ff">int</font> n = mas.size(); </li> <li>  vector<<font color="#0000ff">int</font>> tmp(n); </li> <li>  <font color="#0000ff">int</font> min_size = get_min_size(n); </li> <li>  <font color="#0000ff">int</font> beg = 0, size = min_size; </li> <li>  vector<segment> seg; </li> <li>  seg.reserve((n-1)/min_size + 1); </li> <li>  </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=0;i<n;i+=min_size) { </li> <li>    size = min(min_size,n-i); </li> <li>    selection_sort(mas,i,i+size);  </li> <li>    seg.push_back(segment(i,size)); </li> <li>    try_merge(mas, seg, tmp); </li> <li>  } </li> <li>  <font color="#0000ff">while</font> (seg.size() != 1) { </li> <li>    try_merge(mas, seg, tmp, <font color="#0000ff">true</font>); </li> <li>  } </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p align="justify"><font face="Courier New">P.S: Признаюсь я изначально не возлагал больших надежд на эту сортировку(особенно на свою эффективную реализацию), но должен признать, что был не прав. Данная реализация зашла за 0.061 с, в то время, когда быстрая работал за 0.059 с. Учитывая, что в данную реализацию можно добавить копирование меньшего подмассива + дописать бинарный поиск по не возрастанию, данная сортировка становится пожалуй лучшей для сортировки случайного набора данных. Разработчики Python не могли ошибаться =).</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com5tag:blogger.com,1999:blog-9149260308162775442.post-84146736227704575642011-12-19T19:43:00.001+04:002011-12-19T19:44:00.368+04:00Минимальный циклический сдвиг<p><font face="Courier New"><font size="4"><strong><u>Задача</u></strong>: “Дается строка <strong>S</strong>. Длина S не превышает <strong>1e5</strong>. Необходимо найти <strong>минимальный</strong> в лексикографическом порядке <strong>циклический сдвиг строки S</strong>”.</font></font></p> <p align="center"><font face="Courier New"><strong><font color="#ff0000" size="3">1.Полиномиальные хеш-функции. <br /></font></strong></font><font face="Courier New">По мотивам <a href="https://sites.google.com/site/slipstak2/phashes.ppt?attredirects=0&d=1"><strong><u>презентации</u></strong></a> Александра Скиданова</font></p> <p><font face="Courier New">Рассмотрим строку S = “abcdabb” <br />h(L) – полиномиальная хеш-функция от префикса строки S длины L. <br /><img style="background-image: none; border-right-width: 0px; padding-left: 0px; padding-right: 0px; display: inline; float: left; border-top-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 0px" border="0" align="left" src="https://lh3.googleusercontent.com/-p-UBlhcBtgo/Tu9PYk5DQJI/AAAAAAAAB5E/l_QLrXPA7Qk/s192/hash0.png" /> <br /> <br /> <br /> <br />h(0) = h(“”)        = 0 <br />h(1) = h(“a”)       = a <br />h(2) = h(“ab”)      = a*x<sup>1</sup> + b <br />h(3) = h(“abc”)     = a*x<sup>2 </sup>+ b*x<sup>1</sup> + c <br />h(4) = h(“abcd”)    = a*x<sup>3 </sup>+ b*x<sup>2</sup> + c*x<sup>1</sup> + d <br />h(5) = h(“abcda”)   = a*x<sup>4 </sup>+ b*x<sup>3</sup> + c*x<sup></sup><sup></sup><sup>2</sup> + d*x<sup>1</sup> + a <br />h(5) = h(“abcdab”)  = a*x<sup>5 </sup>+ b*x<sup>4</sup> + c*x<sup>3</sup> + d*x<sup>2</sup> + a*x<sup>1</sup> + b <br />h(5) = h(“abcdabb”) = a*x<sup>6 </sup>+ b*x<sup>5</sup> + c*x<sup>4</sup> + d*x<sup>3</sup> + a*x<sup>2</sup> + b*x<sup>1</sup> + b <br /> <br />Рекурсивно полиномиальную хеш-функцию h(L) можно выразить так: <br /> <br /><img style="background-image: none; border-right-width: 0px; padding-left: 0px; padding-right: 0px; border-top-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 0px" border="0" src="https://lh5.googleusercontent.com/-MnWaYtk5pv8/Tu9SowY8HZI/AAAAAAAAB5Q/HWyYvs5zHxg/s217/hash1.png" /></font><strong><font size="4"><sub> <br /></sub></font></strong><font size="4"><font size="2"><font face="Courier New">H(a,b)- полиномиальная хеш-функция от подстроки S в интервале [a,b) <br /></font></font><font size="4"><strong><font face="Courier New"><img style="background-image: none; border-right-width: 0px; padding-left: 0px; padding-right: 0px; border-top-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 0px" border="0" src="https://lh4.googleusercontent.com/-ZhLb99ga7Pw/Tu9SowqnMJI/AAAAAAAAB5U/kupp0DuV6Y8/s260/hash2.png" /></font></strong><sup><strong> <br /></strong></sup></font><font size="2" face="Courier New">Следовательно можно получать полиномиальные хеш-функции от любой подстроки S за O(1). <br /> <br />Пусть len – длина строки S. <br />Возвращаемся к первоначальной задачи. Чтобы найти минимальный циклический сдвиг строки S: <br />1) Модифицируем исходную строчку S = S + S. <br />2) Считаем полиномиальную хеш-функцию h(L) для всех префиксов строки S. <br />3) На текущем шаге наилучший ответ на поставленную задачу – это подстрока строки S длины len, начинающаяся c позиции best = 0. <br />4) Последовательно перебираем все возможные начальные позиции cur в интервале [1,len) <br />5) Бинарным поиском подбираем длину общего префикса для наилучшего текущего ответа, начинающегося с позиции best, и кандидата на это место, начинающегося с позиции cur. <br />6) Сравниваем первые различные символы двух образцов. Если у текущего кандидата на этой позиции стоит символ с меньшим кодом, тогда обновляет наилучший ответ. <br /></font></font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li>typedef unsigned <font color="#0000ff">long</font> <font color="#0000ff">long</font> UINT; </li> <li><font color="#0000ff">int</font> min_cycle_shift(<font color="#0000ff">char</font> *s, <font color="#0000ff">int</font> init_len) { </li> <li>  UINT *hash = <font color="#0000ff">new</font> UINT[2*init_len]; </li> <li>  hash[0] = 0; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> i=1;i<2*init_len;++i) </li> <li>    hash[i] = x * hash[i-1] + s[i-1]; </li> <li>  </li> <li>  <font color="#0000ff">int</font> bst_pos = 0; </li> <li>  <font color="#0000ff">for</font> (<font color="#0000ff">int</font> cur_pos = 1; cur_pos < init_len; ++cur_pos) { </li> <li>    <font color="#0000ff">int</font> l = 0, r = init_len-1, res = 0; </li> <li>    <font color="#0000ff">while</font> (l <= r) { </li> <li>      <font color="#0000ff">int</font> len = (l + r) >> 1; </li> <li>      UINT hash_bst = hash[bst_pos + len] - hash[bst_pos] * _pow[len]; </li> <li>      UINT hash_cur = hash[cur_pos + len] - hash[cur_pos] * _pow[len]; </li> <li>      <font color="#0000ff">if</font> (hash_bst == hash_cur) { </li> <li>        res = len; </li> <li>        l = len + 1; </li> <li>      } </li> <li>      <font color="#0000ff">else</font> { </li> <li>        r = len - 1; </li> <li>      } </li> <li>    } </li> <li>    <font color="#0000ff">if</font> (s[bst_pos + res] > s[cur_pos + res]) </li> <li>      bst_pos = cur_pos; </li> <li>  } </li> <li>  delete[] hash; </li> <li>  <font color="#0000ff">return</font> bst_pos + 1; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p> <table border="0" cellspacing="0" cellpadding="2" width="376"><tbody> <tr> <td width="225"><font face="Courier New">Сложность данного решения:</font><strong> </strong></td> <td width="149"><strong><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh4.googleusercontent.com/-KnD-024nNCw/Tu9Y_uCt7LI/AAAAAAAAB5o/oTrVWg4ZGEw/s126/hash3.png" /></strong></td> </tr> </tbody></table> <br /><font face="Courier New">P.S: В качестве x нужно использовать небольшое простое число. Например 11. <br />P.S.S: Все вычисления ведутся без модульной арифметики. Поэтому интервал возможных значений полиномиальной хеш-функции равен 2<sup>64</sup>.</font></p> <p align="center"><strong><font color="#ff0000" size="3" face="Courier New">2. Алгоритм Дюваля</font></strong></p> <p align="justify"><font color="#000000"><font face="Courier New">Все что нужно - написано на </font><a href="http://e-maxx.ru/algo/duval_algorithm"><strong><u><font face="Courier New">e-maxx’e</font></u></strong></a><font face="Courier New">. Приведу просто фрагмент кода, решающую ту же самую задачу. <br /></font></font></p> <blockquote><code><font color="#000000" size="2" face="Courier New"> <ol> <li><font color="#008000">// s уже равна s+s</font> </li> <li><font color="#0000ff">int</font> min_cycle_shift(<font color="#0000ff">char</font> *s, <font color="#0000ff">int</font> len) { </li> <li>  <font color="#0000ff">int</font> i = 0, ans = 0; </li> <li>  <font color="#0000ff">while</font> (i < len/2) { </li> <li>    ans = i; </li> <li>    <font color="#0000ff">int</font> k = i, j = i+1; </li> <li>    <font color="#0000ff">while</font> (j < len && s[k] <= s[j]) { </li> <li>      <font color="#0000ff">if</font> (s[k] < s[j]) </li> <li>        k = i; </li> <li>      <font color="#0000ff">else</font> </li> <li>        ++k; </li> <li>      ++j; </li> <li>    } </li> <li>    <font color="#0000ff">while</font> (i<=k) </li> <li>      i += j - k; </li> <li>  } </li> <li>  <font color="#0000ff">return</font> ans + 1; </li> <li>} </li> </ol> </font><font color="#808080" size="1">* This source code was highlighted with <a href="http://virtser.net/blog/post/source-code-highlighter.aspx"><font color="#808080" size="1">Source Code Highlighter</font></a>.</font></code></blockquote> <p><font face="Courier New"> <table border="0" cellspacing="0" cellpadding="2" width="298"><tbody> <tr> <td width="221">Сложность данного решения:</td> <td width="75"><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; border-top: 0px; border-right: 0px; padding-top: 0px" border="0" src="https://lh6.googleusercontent.com/-5aZ2TOMlwcY/Tu9Y_Zha-HI/AAAAAAAAB5k/4xgLcQvTaLI/s57/hash4.png" /></td> </tr> </tbody></table> </font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-67321794885775083182011-12-12T20:35:00.001+04:002011-12-13T01:06:58.719+04:00Сортировка большого файла с целыми числами: Генератор тестов (Часть 1)<p align="justify"><font size="3" face="Courier New"><a href="http://cppalgo.blogspot.com/2011/12/blog-post.html"><strong>[Все части]</strong></a> <br /><a href="http://cppalgo.blogspot.com/2011/12/0_12.html"><strong>[Прошлая часть: Вводное слово]</strong></a> <br /> <br /><font size="2">Итак, чтобы удобнее было готовится к нашему состязанию, была разработана небольшая утилита для генерации тестов. <br />При запуске утилиты <strong><font size="3">big_sort_tests_gen.exe</font></strong> мы видим следующую таблицу. <br /><img style="display: block; float: none; margin-left: auto; margin-right: auto" src="https://lh6.googleusercontent.com/-ZtGcG9ncFis/TuYrbRPBmNI/AAAAAAAAB4k/8SD-bQryVbo/s677/gen4.png" /> <br />После того, как все настройки выставлены, вводим команду <strong><font size="3">–start</font></strong>. <br /> <br />Общий механизм работы утилиты: <br />На первом этапе все числа равномерно распределяются между между временными файлами. После чего запускаются независимые потоки, в которых генерируются временные файлы с тем количеством чисел, которые файл получил во время распределения:</font></font><font size="3" face="Courier New"><font size="2"> <br /><img style="display: block; float: none; margin-left: auto; margin-right: auto" src="https://lh4.googleusercontent.com/-w0NNCEWf2xE/TuYo4HJCZSI/AAAAAAAAB4A/p7IG545vCdQ/s677/gen0.png" />На втором этапе все временные файлы сливаются в один: <br /><img style="display: block; float: none; margin-left: auto; margin-right: auto" src="https://lh6.googleusercontent.com/-HX2vCRU3P0Y/TuYo3ywjmiI/AAAAAAAAB38/YE5gOHuXaVQ/s677/gen1.png" />После выполнения первых двух этапов мы получаем информацию о времени, которое было затрачено на их выполнение: <br /><img style="display: block; float: none; margin-left: auto; margin-right: auto" src="https://lh3.googleusercontent.com/-Yg_OxejRoXk/TuYo4NVTJhI/AAAAAAAAB4E/Sgy-jTP5VSM/s677/gen2.png" />Корректность сгенерированного файла можно проверить с помощью команды <strong><font size="3">–check</font></strong>: <br /><img style="display: block; float: none; margin-left: auto; margin-right: auto" src="https://lh6.googleusercontent.com/-MONdags7c1M/TuYo4p1z8YI/AAAAAAAAB4M/irZ4tIEwSkU/s677/gen3.png" />Если файл сгенерирован, согласно требованиям условия задачи(см. <a href="http://cppalgo.blogspot.com/2011/12/0_12.html"><strong><u>Прошлый пост: Вводное слово</u></strong></a>), то появится “OK!”. В противном случае будет выведено описание ошибки. <br /> <br />Все сгенерированные файлы записывают в директорию test, расположенную вместе с исполняемым файлом утилиты. <br /> <br />О настройках генератор довольно популярно изложено в следующем видео: <br /></font></font> <div style="padding-bottom: 0px; padding-left: 0px; width: 448px; padding-right: 0px; display: block; float: none; margin-left: auto; margin-right: auto; padding-top: 0px" id="scid:5737277B-5D6D-4f48-ABFC-DD9C333F4C5D:54f2f3d2-1cd8-4e07-9432-07c919cf0a5c" class="wlWriterEditableSmartContent"><div id="3d006b1c-b336-4d5c-ad41-eb354933c769" style="margin: 0px; padding: 0px; display: inline;"><div><a href="http://www.youtube.com/watch?v=nyxuqVWQ-Ac" target="_new"><img src="http://lh3.ggpht.com/-fMMVX4JF_Aw/TuZs8fJviPI/AAAAAAAAB44/kiCoDbg4VR8/video32b549061c87%25255B11%25255D.jpg?imgmax=800" style="border-style: none" galleryimg="no" onload="var downlevelDiv = document.getElementById('3d006b1c-b336-4d5c-ad41-eb354933c769'); downlevelDiv.innerHTML = "<div><object width=\"448\" height=\"336\"><param name=\"movie\" value=\"http://www.youtube.com/v/nyxuqVWQ-Ac?hl=en&hd=1\"><\/param><embed src=\"http://www.youtube.com/v/nyxuqVWQ-Ac?hl=en&hd=1\" type=\"application/x-shockwave-flash\" width=\"448\" height=\"336\"><\/embed><\/object><\/div>";" alt=""></a></div></div></div> </p> <p><font face="Courier New">Исходник генератора (проект MS VS 2008, Win32, C++): </font><a href="http://tinyurl.com/cvm6s3a"><font face="Courier New">http://tinyurl.com/cvm6s3a</font></a> <br /><font face="Courier New">Бинарники генератора + окружение(Win32): <a href="http://tinyurl.com/c9qch5v">http://tinyurl.com/c9qch5v</a> <br />Откомпилированный генератор под Linux ждем от Сагунова Данила.</font></p> <p><font face="Courier New">Если у Вас возникли вопросы, предложения, замечания. Будем рады их услышать</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-61842241909719562122011-12-12T19:51:00.001+04:002011-12-13T13:37:23.339+04:00Сортировка большого файла с целыми числами: Вводное слово (Часть 0)<p align="justify"><font face="Courier New"><a href="http://cppalgo.blogspot.com/2011/12/blog-post.html"><strong><font size="3">[Все части]</font></strong></a> <br /><font size="3"><strong><a href="http://cppalgo.blogspot.com/2011/12/1.html">[Следующая часть: Генератор тестов]</a> <br /></strong></font> <br />Не так давно родилась идея организовать небольшое состязание на самое быстрое решение следующей задачи. <br /></font><font face="Courier New"> <br /><strong><font color="#ff0000">Условие задачи: <br /></font></strong>Входной текстовый файл <strong>input.txt</strong> содержит набор из N 32-ух битных знаковых чисел, разделенных между собой ровно одним пробелом. Необходимо отсортировать числа из входного файла и записать их во выходной файл <strong>output.txt</strong>. <strong>1<=N<=1e9</strong>. <br /> <br /><strong><font color="#ff0000">Регламент:</font></strong> <br /><strong>0.</strong> Приглашаются к участию все желающие. Вне зависимости от города проживания и возрастной группы. <br /> <br /><strong>1.</strong> Решение участника должно быть представлено в виде exe файла, скомпилированного под Windows. Файлы input.txt и output.txt будут находиться в той же директории, что и исполняемый файл. Допускается наличие любых сторонних файлов(библиотеки, конфиги и пр.) вместе и исполняемым файлом. <br /> <br /><strong>2.</strong> Программа может рассчитывать на: <br />1) HDD: 10 GB <br />2) RAM: 128 MB <br /></font><font face="Courier New"> <br /><strong>3.</strong> Проверяться решение будет на ноутбуке со следующими параметрами: <br />1) Процессор: Intel Core2Duo T5250 1.5GHz (Параметры железа могут измениться) <br />2) Платформа: Windows 7 (x86) <br />3) Файловая система: NTFS <br /> <br /><strong>4.</strong> Решение считается зачтенным, если оно успешно прошло все заготовленные тесты и не выкинуло ни одного исключения. На каждом тесте программа будет запускаться 10 раз. Результатом работы программы будет усредненное время. Если программа во время своей работы использовала лишнеее место на жестком диске или лишнюю оперативную память, то оно штрафуется. Зачтенные решения ранжируются по времени работы. Побеждает самое быстрое решение.</font><font face="Courier New"> <br /> <br /><strong>5.</strong> Решения можно реализовывать на любом языке программирования, использовать любые сторонние библиотеки. Главное, чтобы с исполняемым файлом шел весь набор библиотек. <strong><font color="#ff0000">Если будет замечено вредительство со стороны программы: –10 к карме автора решения. <br /> <br /></font></strong>6. Максимальный срок подачи решения 15 января 2012 (Возможно продление этого срока по желанию участников, т.к. в это время будет проходить сессия у студентов и подготовка к областной олимпиаде по информатике у школьников). <br /> <br /><strong><font color="#ff0000">Главный приз:</font></strong> <font color="#ffc000" size="3"><strong>1 Euro</strong></font> и признание со стороны товарищей(<strong><font color="#ff0000">бесценно</font></strong>). <br />По итогу состязания будет разбор общих подходов к решению подобных задач(о нем будет сказано в последующих частях). <br /> <br />Все вопросы и пожелания пишите здесь в комментариях или в группе: <a href="http://vkontakte.ru/club13315512">http://vkontakte.ru/club13315512</a></font></p> <p><a href="http://cppalgo.blogspot.com/2011/12/1.html"><font size="3" face="Courier New"><strong>[Следующая часть: Генератор тестов]</strong></font></a></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0tag:blogger.com,1999:blog-9149260308162775442.post-37421143716093260262011-12-12T19:40:00.001+04:002011-12-19T20:14:29.031+04:00Сортировка большого файла с целыми числами<p align="justify"><font face="Courier New"><strong><font size="3">Текущий список участников:</font></strong> <br />1. Беляев Игорь     (г. Астрахань – АГТУ - аспирант) <br /></font><font face="Courier New">2. Бородин Виталий  (г. Астрахань – АГТУ - студент) <br /></font><font face="Courier New">3. Елизаров Дмитрий (г. Астрахань – АГТУ - аспирант)</font> <br /><font face="Courier New">4. Сагунов Данил    (г. Астрахань – АТЛ  - школьник) <br />5. Степанов Павел   (г. Астрахань – АГТУ - студент) <br />6. Чаплыгин Андрей  (г. Астрахань - разработчик) <br /></font> <br /><font face="Courier New"><font size="3"><strong><a href="http://cppalgo.blogspot.com/2011/12/0_12.html">Часть 0: Вводное слово.</a></strong></font> <br />Описывается регламент состязания: условие задачи, параметры железа и критерии правильности решения. <br /> <br /><strong><font size="3"><a href="http://cppalgo.blogspot.com/2011/12/1.html">Часть 1: Генератор тестов</a> <br /></font></strong>Представлена утилита, генерирующая тесты, согласно описанной задаче. Можно задавать диапазон генерируемых чисел.</font></p> slipstak2http://www.blogger.com/profile/15957109470497214310noreply@blogger.com0