Тренировка #11 [Меньшиков]

[Условия задач]                   [Список тренировок]

11A. Последовательность
[seq]
Довольно любопытная задача на выявление закономерности в последовательностях. Первый раз всплывает принцип Дирихле.
11B. Провода
[cable]
Классический пример задач на “Бинарный поиск по ответу”. Эта тема хорошо описана в 3 лекции курса Михаила Густокашина
11C. Палиндромы
[palindr]
Двумерное ДП. Один из тех удачных примеров, доказывающий, что ДП много не бывает. Придется немножко подумать.

Тренировка #10 [Меньшиков]

[Условия задач]                    [Список тренировок]

10A. Анти-QuickSort
[antiqs]
Нетипичная задача, требующая глубокого понимания работы быстрой сортировки.
10B. Строки Фибоначчи
[fibostr]
Классная задача на ДП. В наличием определенного опыта в решении подобных задач не представляет больших сложностей. Но есть ряд нюасов, которые нужно учесть.
10C. Игра в зачеркивание
Задача, которая не давала спокойно жить 2 дня. На нее было получено 4 решения, а все описание изложено в отдельном посте
[crossgam] TLE
[crossgam] ДП с запоминанием + vector   [0.105 с.]
[crossgam] ДП с запоминанием + multiset [0.322 с.]
[crossgam] на основе функции Grundy
10D. Граница многоугольника
[border]
Задача скорее на знания, чем на умения. Используем тот факт, что у прямоугольного треугольника количество точек с целочисленными координатами на гипотенузе равно НОД’у(Наибольшему общему делителю) катетов + 1. Представив каждую сторону за гипотенузу, обходим все стороны и получаем результат.
10E. Путь спелеолога
[speleo]
Задача на пространственное воображение и на трехмерный BFS. Особых сложностей быть не должно. Главное не забыть что здесь будет 6 измерений, в отличии от двумерного случая.
10F. Дырявая ткань
[holey]
Предложенное решение сделано полностью по авторскому разбору. Стоит обратить внимание на “приемчик”, как избежать TLE на максимальном тесте.


[Все решения]

10С–Игра в зачеркивание [Меньшиков]

[Тренировка 10]                      [Список тренировок]

Крайне любопытная задача.
Расскажу как мне далось ее решение. Рассказ будет не очень коротким, поэтому наберитесь терпения.

Итак мое первое решение было довольно тривиальным. Основывалось оно на опыте предыдущих задач. Суть заключалось в следующем:

1) Каждое состояние кодировалось числом. (X – единичка, O - нолик). В итоге получается 40 битное число, поэтому оно хранилось в типе long long.
2) Строилась матрица смежности, т.е. матрица переходов. Для каждого числа хранился список чисел, в которые можно попасть из текущего состояния.
3) Также отдельно хранился список всех возможных состояний(чисел) в игре.
4) После чего сортируем массив из п. 3) в порядке возрастания и начинаем его заполнять с конца.
5) Ответ будет находится в первом элементе массива из п. 3)

Чтож – неплохой план! Кодируем. Получаем нечто похожее на это. Каков же вердикт? На 9-и тестах из 31 получаем TLE.

И только после этого я начал ДУМАТЬ!

Тренировка #9 [Меньшиков]

[Условия задач]                   [Список тренировок]

9A. Диалог компьютеров
[dialogue]
Первая задача на моделирование процесса. Большое, немного непонятное условие(на первый взгляд), поэтому советую его читать несколько раз. Тщательно продумываем структуры данных перед тем, как начинать писать.
9B. Бросание кубика
[die]
Первая задача на теорию вероятностей. Для начала вспомним правило сложение вероятностей, и когда его нужно применять. Здесь изложена суть. Понятно, что если с двух бросков шестигранного кубика было набрано 8 очков, то это могло случиться, если выпала одна из комбинаций: 2-6, 3-5, 4-4, 5-3, 6-2. Находим вероятность каждой из этой комбинации и плюсуем в итоговую.

Алгоритм быстрой оболочки (Quick hull)

Рассмотрим алгоритм построения выпуклой оболочки, основанный на принципе разделяй и властвуй. По своей сути этот алгоритм является аналогом быстрой сортировки для задачи упорядочивания элементов в массиве. Отсюда такое название.

Вся представленная реализация основана на описании с wikipedia. Оттуда же можно узнать смысл таинственных переменных S1 и подобных. В качестве “подопытной задачи” была выбрана все та же 5D. Выпуклая оболочка из сборника задач Меньшикова.

Итак пошагово рассмотрим алгоритм.
На начальном этапе мы имеем множество точек на плоскости

Тренировка #8 [Меньшиков]

[Условия задач]                    [Список тренировок]

8A. Несоставляемое число
[nosum]
Хорошая задача, сродни Рюкзаку. Нужно быть внимательным и не ошибиться с выбором типа данных для хранения ответа.
8B. SMS
Очень хорошая задача, которая является логическим продолжением серии задач на динамическое программирование. Первая задача на двумерное ДП. Над ней думал пару дней, в результате чего получилось следующее решение:
[sms] локаничная запись
В книге Павловской вычитал следующий девиз: “Better simpler than clever” (лучше по-простому, чем по-умному). В результате чего увидел в авторском разборе более понятную реализацию, которая делает тоже самое:
[sms] понятная запись
8C. Дерево игры
[gametree]
3-я задача на тему антагонистические игры. Не должна вызывать серьезных затруднений. Решается по аналогии с  предыдущими задачами. В ходе решения явно использовалась рекурсия. Если по условию задачи видно, что глубина рекурсии будет непозволительно большой, то можно модернизировать решение до неявного использования рекурсии или, если это поможет, увеличить глубину стека. Мы такое уже делали раньше.
8D. Дуга на сфере
[spherarc]
Задача на знание формул. А формулы, как говорится, надо знать или уметь их выводить.
8E. Путь коня
[knightw]
Эта задача уже была подробно рассмотрена в тренировках Михаила Долинского. Но решить ее еще раз будет крайне полезно.
8F. Грядки
[beds]
Очередная задача на DFS/BFS. Долго не мог понять, зачем автор дал столько много однотипных задач. Но когда ознакомился с разборами стало ясно, что на маленьких ограничениях можно успешно сдать решение с большой алгоритмической сложностью, но более лаконичной записью. В наших разборах я их не упомянул, поэтому всех заинтересовавшихся перенаправляю в книгу.  

[Все решения]

Двусвязный список [List]

[Все типы данных]

Рассматриваемые темы:
1. Что такое двусвязный список
2. Как хранится двусвязный список в памяти компьютера?
3. Реализация базовых операций
4. Оценка сложности базовых операций

Первые два пункта очень подробно освещены в литературе:
1) Для общего представления читаем Википедию.
2) Для более детального и наглядного изучения Окулов. Абстрактные типы данных
3) Очень хорошее описания языка С++ и динамических структур данных можно найти в книге Павловской

Договоримся, что в дальнейшем речь будет идти о двусвязном списке, в котором каждый узел будет хранить 4 байтное целочисленное значение.

На третьем пункте остановимся по поподробней.
Для начала рассмотрим класс, описывающий элемент списка:

1. class ListNode
2. {
3. public:
4.   int value;
5.   ListNode *next;
6.   ListNode *prev;
7. };

* This source code was highlighted with Source Code Highlighter.

Надеюсь комментарии излишни. Но если остались вопросы, возвращаемся к первым двум пунктам и еще раз внимательно читаем теорию.
Теперь рассмотрим класс, описывающий сам двусвязный список:

1. class List
2. {
3. private:
4.   ListNode* _pBegin;
5.   ListNode* _pEnd;
6.   unsigned int _size;
7. };

* This source code was highlighted with Source Code Highlighter.

Интуитивно можно догадаться о смысле каждого из полей. Двигаемся дальше. Составим список функций, которые мы хотим реализовать для двусвязного списка, которые будут являться методами класса List:

1. List();
2. List(int size);
3. List(int size, int data);
4. void assign(int data); // инициализация всего списка значением data
5. ListNode* back(); //указатель на конец
6. ListNode* begin(); // указатель на начало
7. bool empty(); // проверка на пустоту
8. ListNode* erase(ListNode* pWhere); // удалить узел
9. ListNode* find(int data); // найти первый узел, содержащий data
10. ListNode* insertBefore(ListNode* Where, int data); // вставка до
11. ListNode* insertАfter(ListNode* Where, int data); // вставка после
12. void output(); // вывод
13. bool pop_back(); // удаление с конца
14. bool pop_front(); // удаление с начала
15. void push_back(int data); // добавление в конец
16. void push_front(int data); // добавление в начало
17. bool remove(int data); // удалить все узлы, содержащие такую data
18. void resize(unsigned int newLen); // изменить размер
19. void reverse(); // реверснуть список
20. unsigned int size(); // размер списка
21. void Swap(ListNode* a, ListNode* b); // обмен двух элементов местами

* This source code was highlighted with Source Code Highlighter.

Список функций был разработан согласно набору функций класса list из STL, который является аналогом нашего разрабатываемого класса. Вместо итераторов мы будет использовать указатели на узлы списка. Разрабатываемый класс List в первую очередь должен дать ответы на вопросы – как устроены базовые операции и как эффективно их можно реализовать самостоятельно. В реальных боевых условиях рекомендуется использовать std::list<T>, хотя могут быть случаи, когда использование нашего класса List может привести к ускорению работы программы.

Предлагаю ознакомится с полной реализацией двусвязного списка на примере класса List:
ListNode.h
List.h
List.cpp

Самая замудренная операция оказалась void Swap(ListNode* a, ListNode* b). Если Вы можете предложить более изящную реализацию этой операции – будет крайне интересно с ней ознакомиться.

Алгоритмические сложности базовых операций:

1) Получение элемента по индексу	O(N)
2) Добавление элемента в конец	O(1)
3) Добавление элемента в начало	O(1)
4) Добавление элемента в “середину”	O(1), если известно место, иначе O(N)
5) Удаление элемента с конца	O(1)
6) Удаление элемента с начала	O(1)
7) Удаление элемента с “середины”	O(1), если известно место, иначе O(N)

Тренировка #7 [Меньшиков]

[Условия задач]                    [Список тренировок] 

7A. Упорядоченные дроби
[ordfrac] Лобовая реализация
Т.к. число N не превышает 255, то общее количество дробей будет невелико, поэтому можно получить все дроби двойным циклом, отбрасывая “повторки”.
[ordfrac] Ряд Фарея
Ряд Фарея предоставляет механизм генерации нужного ряда дробей сразу в отсортированном виде
7B. Сообщение
[message]
ДП + длинная арифметика. Подобная задача и некоторые ее вариации часто встречаются на школьных контестах.
7C. Игра умножения
[multgame] ДП с использованием map
Очередная задача на антагонистические игры. Чуть более сложней чем предыдущая 6С. Данная реализация более лаконичная, но требует логарифмического времени для получения ответа к решенной подзадаче.
[multgame] ДП + бинарный поиск
Разница от предыдущей реализации в том, что все возможные шаги в игре находятся в одном массиве. Тем самым задача по своей сути сводится к задаче 6С. Но тем не менее получение ответа на решенную подзадачу также выполняется за логарифмическое время, т.к. при этом приходится использовать бинарный поиск.
7D. Прямая и квадраты
[sqline] O(N*N)
Квадратичная реализация, наиболее уместная для предложенных ограничений. Используем факт, что прямая не пересекает многоугольник тогда и только тогда, когда он полностью находится либо в правой, либо в левой полуплоскости от прямой.
[sqline] O(N)
Линейная реализация, которая требует внимательности и аккуратности. Необходимо учесть 3 случая: горизонтальная, убывающая и возрастающая прямая. Будем двигаться по прямой небольшими шагами, равными стороне маленького квадрата, вдоль оси X. При этом будем анализировать значения Y. Рассмотрим 3 основных случая для возрастающей прямой:

	Прямая пересекает только один квадрат
	Прямая пересекает два квадрата
	Прямая пересекает 4 квадрата

Остальные случае предлагается рассмотреть самостоятельно.
7E. Lines(2)
[lines2]
Решение, аналогичное задаче 6E.Lines
7F. Удаление клеток
[remsquar]
Несложная задача. В качестве основных алгоритмов, решающих эту задачу на ум приходят DFS и BFS. Оба имею квадратичную сложность, но DFS писать проще. Торопится не стоит. Размерности матрицы таковы, что придется делать 250*250 рекурсивных вызовов. Поэтому вовремя одумываемся и быстро пишем BFS.


[Все решения]

Тренировка #6 [Меньшиков]

[Условия задач]                   [Список тренировок] 

6A. Закраска прямой 
[cover]
Полезная задача. Является фундаментальным “кирпичиком”. Другая вариация этой задачи встречается в задаче Музей. Нужно научиться корректно, а главное быстро обрабатывать случай когда часть отрезка принадлежит нескольким интервалам, а также грамотно откидывать пустоты. 
6B. Суммы
[sums]
Переборная задача, требующая знания и понимая “Рюкзака”.
6C. Игра “Даты”
[dategame]
Первая задача на теорию игр. Крайне полезно при первом прорешивании догадаться самому до правильного решения, воспользовавшись фактом, что решается она методом Динамического программирования. Мне такого сделать не удалось. Текущая позиция для первого игрока является выигрышной, если есть хотя бы одна позиция, куда он может пойти, которая является проигрышной для второго игрока.
6D. Площадь прямоугольников
[rectarea]
Эта задача еще один фундаментальный “кирпичик”. Ее решение изложено в книге Окулова. Рассмотрим рисунок.
Как видно дано 4 прямоугольника. Каждый из них дает по 2 проекции на оси X и Y. Избавляемся от дубликатов проекций. После чего получаем сетку, образованную этими проекциями. Эта сетка разбила первоначально пустой прямоугольник на N маленьких прямоугольников. В нашем случае N = 28. Чтобы найти суммарную площадь нужно перебрать каждый прямоугольник сетки и проверить, не является ли он вложенным хотя бы в один из первоначальных прямоугольников.
6E. Lines
[lines]
Отличная задача на одновременное применение поиска в ширину(BFS) для получения наилучшего ответа и поиска в глубину(DFS) для восстановление ответа.
6F. Покраска лабиринта
[paintlab] Рекурсивный DFS
Эту задачу можно делать как поиском в глубину, так и в ширину. Т.к. ограничения невелики и DFS пишется быстрее, то выбираем именно этот путь.
[paintlab] Нерекурсивный DFS
Была предпринята попытка показать, как можно реализовать DFS без явного использования рекурсии. Для этого был использован стек, в котором хранились предыдущие состояния. На больших размерностях такой подход будет работать быстрее. Но в боевых условиях, чтобы избежать использования рекурсии лучше писать BFS, если это возможно.


[Все решения]

Тренировка #5 [Меньшиков]

[Условия задач]                   [Список тренировок] 

5A. Дружественные числа 
[friendly] Precalc
Лобовое решение не проходит по времени. Поэтому воспользуемся “грязным приемчиком”, и подсчитаем все что нам нужно заранее и запишем все ответы в исходник.
5B. Скобки(2)
[brackets2]
Крайне полезная задача на понимание работы рекурсии. Рекурсивно получаем следующую скобочную последовательность. На каждом шаге храним количество открытых скобок и позицию, куда нужно ставить очередную скобку. Для получения корректных скобочных последовательностей нужно хранить стек, со всеми незакрытыми скобками.

А.Шень “Программирование. Теоремы и задачи”

Одна из лучших книг по алгоритмам (если не лучшая), которую мне доводилась читать.
Отличная подборка задач по всем предложенным темам. Предлагаемые задачи заставляют мыслить неординарно. По всем задачам есть рекомендации к решению. Ко многим задачами приведены решения на языке Pascal.

Крайне рекомендую читать оригинал.

1.3 “Индуктивные функции” (по А.Г. Кушниренко)

А.Шень “Программирование. Теоремы и задачи”

1.3.2
1.3.3
1.3.4
1.3.5

1.2. “Массивы”

А.Шень “Программирование. Теоремы и задачи”

1.2.1 (Обнуление массива) 
Вариант 1:

1. int mas[max_size] = {0};

Вариант 2:

1. int mas[max_size];
2. memset(mas,0,sizeof(int) * max_size);

1.2.2 (Подсчет количества объектов) 

1. int mas[max_size];
2. . . .
3. int zeroesAmount = 0;
4. for (int i=0;i<max_size;i++)
5.   zeroesAmount += mas[i] == 0 ? 1 : 0;

Массив [Array]

[Все типы данных]

Рассматриваемые темы:
1. Что такое массив?
2. Как хранится массив в памяти компьютера?
3. Оценка сложности базовых операций

Абстрактные типы данных

По мотивам одноименной книги Станислава Окулова с тематическими задачами от Александра Шеня(2004).

* Массивы
* Матрицы
* Списки
  * Односвязные
  * Двусвязные
  * Кольцевые
* Стеки
* Очереди
* Множества
  * Системы непересекающихся множеств
  * Словарь
* Очереди с приоритетами
* Деревья
  * Двоичные кучи
  * Биномиальные кучи
  * Дерево Фенвика
  * Дерево отрезков
  * Двоичное дерево поиска
  * Декартово дерево
  * АВЛ - деревья
  * 2-3 деревья
  * Б – деревья
  * Красно-черные деревья

Алгоритм Джарвиса

Теория:   Wikipedia, Hardfire

Практика: Меньшиков – 5D [informatics.mccme.ru]

Визуализатор: rain.ifmo.ru [Java]

Реализация:
Алгоритм Джарвиса позволяет строить выпуклую оболочку на множестве заданных точек. Алгоритмическая сложность O(N*H), где N – общее количество точек, H – количество точек в выпуклой оболочке.

Плавная сортировка (Smooth_sort)

[Все сортировки]

Предварительные темы:
1. Пирамидальная сортировка
2. Битовые операции

Теория: На русском языке мне, к сожалению, не удалось найти ни одного материала по этой теме. Поэтому общее представление об алгоритме можно получить из англоязычного источника, например здесь.
Рекомендую обратить внимание на gif’ку, представленную в статье. Лично мне она очень понравилась).

Битовый операции

Рассмотрим ряд базовых задач на работу с битами числа. В качестве базового целочисленного типа будем использовать 32битный int.

Попрактиковаться можно здесь: задачи на битовые операции.

1. Обнулить последние i бит числа А

1. A>>=i;
2. A<<=i;

или

1. A &= (~0)<<i;

2. 2^n

1. A = 1<<n;

Сортировка Шелла (Shell_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:
Данная сортировка является модификацией сортировки вставками.

Сортировка с помощью бинарного дерева (Tree_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Реализация:

В своей реализации эта сортировка использует структуру данных: бинарное дерево, каждый элемент которого можно описать следующим образом:

1. struct tree
2. {
3.   tree* left; // левый сын
4.   tree* right; // правый сын
5.   int value;  // значение
6. };

* This source code was highlighted with Source Code Highlighter.

Сортировка слиянием (Merge_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Гномья сортировка (Gnome_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Реализация:

1. void gnome_sort(vector<int> &mas)
2. {
3.   int cur = 0;
4.   while (cur + 1 < mas.size())
5.   {
6.     if (mas[cur]<=mas[cur+1])
7.       cur++;
8.     else
9.     {
10.       swap(mas[cur],mas[cur+1]);
11.       cur--;
12.       if (cur<0) cur = 0;
13.     }
14.   }
15. }

* This source code was highlighted with Source Code Highlighter.

Сортировка выбором(Selection_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:

1. void selection_sort(vector<int> &mas)
2. {
3.   for (int i=0;i<mas.size();i++)
4.     for (int j=i+1;j<mas.size();j++)
5.       if (mas[i]>mas[j])
6.         swap(mas[i],mas[j]);
7. }

* This source code was highlighted with Source Code Highlighter.

UPD[29.09.2011]

1. void selection_sort(vector<int> &mas) {
2.   for(int i=0;i<mas.size();i++) {
3.     int minPos = i;
4.     for(int j=i+1;j<mas.size();j++)
5.       if(mas[minPos] > mas[j])
6.         minPos = j;
7.     swap(mas[minPos],mas[i]);
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

P.S: Из всех квадратичных сортировок сортировка выбором имеет самую локаничную запись и сложность O(n*(n-1)/2). Вот почему, мне она нравится больше других квадратичных сортировок)

Сортировка вставками (Insert_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:

1. void insert_sort(vector<int> &mas) {
2.   for (int i=1;i<n;++i) {
3.     for (int j=i;j>0;j--) {
4.       if (mas[j-1] > mas[j])
5.         swap(mas[j-1],mas[j]);
6.       else
7.         break;
8.     }
9.   }
10. }

* This source code was highlighted with Source Code Highlighter.

Шейкерная сортировка (Cocktail_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Реализация:

1. void cocktail_sort(vector<int> &mas)
2. {
3.   int l = 0, r = mas.size()-1;
4.   while (l<=r)
5.   {
6.     // всплывает самый "легкий" элемент
7.     for (int i = r ;i>l;i--)
8.       if (mas[i-1]>mas[i])
9.         swap(mas[i-1],mas[i]);
10.     l++;
11.     // тонет самый "тяжелый элемент"
12.     for (int i=l; i<r; i++)
13.       if (mas[i]>mas[i+1])
14.         swap(mas[i],mas[i+1]);
15.     r--;
16.   }
17. }

* This source code was highlighted with Source Code Highlighter.

Пузырьковая сортировка (Bubble_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:

1. void bubble_sort(vector<int> &mas)
2. {
3.   for (int i=1;i<mas.size();i++)
4.     for (int j = mas.size()-1;j>=i;j--)
5.       if (mas[j-1]>mas[j])
6.         swap(mas[j-1],mas[j]);
7. }

* This source code was highlighted with Source Code Highlighter.

N^N mod 10^P

[Вся длинная арифметика] 

В завершении обзора задач на длинную арифметику рассмотрим эту интересную задачу. Часто при работе с длинными числами бывает нужно получить не все число целиком, а только несколько последних цифр. В таких задачах даже порой можно обойтись вообще без длинной арифметики.

По условию задачи 1<=N<=1e9 и 1<=P<=100.

Квадратный корень из длинного числа

[Вся длинная арифметика]

Эта задача далась мне тяжелее всех. Наверное потому, что я пытался зачесть ее на acm.sgu.ru и acmp.ru, где ограничения на количество разрядов в числе 1000 и 3000 соответственно. Для начала зачтем эту задачу на informatics.mccme.ru, где ограничение всего 100.

Здесь можно пойти двумя путями:

Длинное - короткое

[Вся длинная арифметика]

До того момента, пока не столкнулся с извлечением квадратного корня из длинного числа, был уверен, что реализация этой операции не будет иметь никакого практического значения. Но я ошибался.

Приведенная реализация практически идентична с  реализацией операции “длинное + короткое”:

1. BigInt operator - (const BigInt &a, const int &b)
2. {
3.   BigInt res = a;
4.   int pos = 0;
5.   res.digits[0] -= b;
6.   while (res.digits[pos] < 0)
7.   {
8.     res.digits[pos+1] --;
9.     res.digits[pos++] +=osn;
10.   }
11.   if (res.amount && !res.digits[res.amount-1])
12.     res.amount--;
13.   return res;
14. }

* This source code was highlighted with Source Code Highlighter.

Сортировки

Квадратичные сортировки O(N*N):

Пузырьковая                (Bubble sort)     +
Шейкерная                  (Cocktail sort)   +
Вставками                  (Insert sort)     +
Гномья                     (Gnome sort)      +
Выбором                    (Selection sort)  +


Квазилинейные O(N*log(N)):

Слиянием                   (Merge sort)      +
С помощью двоичного дерева (Tree sort)       -
Сортировка Шелла           (Shell sort)      -
Пирамидальная              (Heap sort)       -
Плавная                    (Smooth sort)     -
Быстрая                    (Quick sort)      -
STL C++                    (Intro sort)      -
Python сортировка          (Tim sort)        +


Линейные O(N):

Подсчетом                  (Counting sort)   +
Карманная                  (Bucket sort)     +
Поразрядная                (Radix sort)      -




* Плюсом отмечены стабильные сортировки

Факториал короткого числа

[Вся длинная арифметика]  

Тип int может поместить в себя не больше 12!.А как же нам быть если нужно найти 100! ? Самое время обратиться к длинной арифметике.
Сама реализация не представляет для нас ничего нового:

1. BigInt fact(int n)
2. {
3.   BigInt res(1);
4.   for (int i=2;i<=n;i++)
5.     res = res * i;
6.   return res;
7. }

* This source code was highlighted with Source Code Highlighter.

По условию задачи n<=3000. В качестве osn лучше выбрать 10000, т.к. в таком случае мы сможем обойтись умножением длинного на короткое.

Пирамидальная сортировка (Heap Sort)

[Все сортировки]

Теория: читаем дивную статью с картинками

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru [Java]

Длинное^короткое (возведение в степень)

[Вся длинная арифметика]

Данную операцию можно решить лобовым перемножением исходного числа, а можно воспользоваться быстрым возведением в степень:

1. BigInt pow(const BigInt &a, const int &N)
2. {
3.   BigInt res(1),cur = a;
4.   int n = N;
5.   while (n)
6.   {
7.     if (n&1)
8.       res = res * cur;
9.     cur = cur * cur;
10.     n>>=1;
11.   }
12.   return res;
13. }

* This source code was highlighted with Source Code Highlighter.

Стоит обратить внимание на то, что количество разрядов у результирующего числа очень быстро растет, поэтому нужно грамотно подбирать размерность массива digits в структуре BigInt.

Длинное DIV длинное & Длинное MOD длинное

[Вся длинная арифметика] 

Пришло время познакомиться с самой “страшной” операцией на длинную арифметику. Первый раз я ее реализовал на Accepted 31 июля 2008. До этого момента мне было даже страшно подумать над ее реализацией. Но как оказалось не так уж это деление и страшно, как его малюют. Мы не будем изобретать велосипед, а просто грамотно, максимально понятно и быстро реализуем деление столбиком. Рассмотрим нижепредставленный рисунок.

Как видно osn = 100.

Длинное DIV короткое & Длинное MOD короткое

[Вся длинная арифметика]

При упоминании операции деления на длинных числах молодые олимпиадники резко меняются в лице, меняя веселые гримасы на хмурые лица. Скорее всего причиной тому являются разговоры более опытных товарищей, когда последние в красках обсуждают деление длинного на длинное. Об этой операции мы поговорим чуть позже. А пока спешу успокоить, т.к. деление длинного на короткое не сложнее, чем умножение длинного на короткое):

Длинное * длинное

[Вся длинная арифметика]

Итак мы подошли к первой операции, реализацию которой можно считать не такой тривиальной, как в предыдущих случаях:

1. BigInt operator * (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   for (int i=0;i<a.amount;i++)
5.   {
6.     int r = 0;
7.     for (int j=0;j<b.amount | r;j++)
8.     {
9.       res.digits[i+j] += a.digits[i] * b.digits[j] + r;
10.       r = res.digits[i+j] / osn;
11.       res.digits[i+j] -= r*osn;
12.     }
13.   }
14.   int pos = a.amount + b.amount;
15.   while (pos>0 && !res.digits[pos])
16.     pos--;
17.   res.amount = pos + 1;
18.   return res;
19. }

* This source code was highlighted with Source Code Highlighter.

Обратим внимание на строчку 11. Т.к. алгоритм квадратичный, то избежание использования операции взятия остатка от деления(%) дает прирост в скорости, более ощутимый, чем для линейных алгоритмов.

Длинное * короткое

[Вся длинная арифметика] 

Умножение длинного числа на короткое является частным случаем умножения длинного на длинное. Но для того, чтобы данная операция работала быстрее общего случая, нужно позаботиться об индивидуальной реализации этой операции:

1. BigInt operator * (const BigInt &a, const int &n)
2. {
3.   BigInt res;
4.   res.amount = a.amount;
5.  
6.   int r = 0;
7.   for (int i=0;i<res.amount | r;i++)
8.   {
9.     res.digits[i] = a.digits[i] * n + r;
10.     r = res.digits[i]/osn;
11.     res.digits[i] -= r*osn;
12.   }
13.   if (res.digits[res.amount])
14.     res.amount++;
15.  
16.   return res;
17. }

* This source code was highlighted with Source Code Highlighter.

Как видно алгоритм линейный. Для ускорения операций в строке 11 мы избежали использования операции взятия остатка от деления(%).

Длинное – длинное(знаковое вычитание)

[Вся длинная арифметика]

Рассмотрим случай знакового вычитания, когда вычитаемое может быть больше уменьшаемого.

Если разрабатывать универсальную библиотеку для работы с длинными числами, то конечно нужно предусмотреть логический признак: положительное число или отрицательное. Это повлечет за собой переделку всех операций.

Имея в наличии реализации всех операций в неотрицательных числах можно реализовать их и с учетом знака.

У меня же стоит цель зачесть задачу на сервере проверки).
Ниже приведена логика работы программы на основе ранее разобранных операций сравнения и беззнакового вычитания:

1. bool isMinus = false;
2. if (a < b)
3. {
4.   c = b - a;
5.   isMinus = true;
6. }
7. else
8.   c = a - b;
9. if (isMinus) cout<<"-";
10. c.output();

* This source code was highlighted with Source Code Highlighter.

Длинное – длинное (беззнаковое вычитание)

[Вся длинная арифметика]

Рассмотрим случай беззнакового вычитания, когда вычитаемое не превосходит уменьшаемого(A-B, A>=B):

1. BigInt operator - (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res = a;
4.   int r = 0;
5.   for (int i = 0;i<res.amount;i++)
6.   {
7.     res.digits[i] -= b.digits[i] + r;
8.     if (res.digits[i]<0)
9.     {
10.       res.digits[i]+=osn;
11.       res.digits[i+1]--;
12.     }   
13.   }
14.   int pos = res.amount;
15.   while (pos && !res.digits[pos])
16.     pos--;
17.   res.amount = pos+1;
18.   return res;
19. }

* This source code was highlighted with Source Code Highlighter.

В реализации данной операции необходимо корректно учесть случай, когда a=b.

P.S: В первой версии выводились лишние ведущие нули. Эту ошибку обнаружил Privalov, за что выражаю ему благодарность.

Сравнение длинных чисел

[Вся длинная арифметика]

Чтобы сравнить длинные числа необходимо и достаточно определить три операции: “больше”, “меньше” и “проверка на равенство”. Отметим важный факт: для реализации задуманного можно реализовать только только одну операцию (или “больше” или “меньше”). Остальные можно выразить из нее.

Длинное + короткое

[Вся длинная арифметика]

Более распространенной операцией сложения является операция “Длинное + длинное”. Если имеем дело с частным случаем, когда одно из слагаемых является длинным числом, а второе строго меньше основания системы счисления (<osn), т.е. является цифрой, то в целях оптимизации и ускорения работы программы следует подумать над более быстрой реализацией.

Представляю свою реализацию:

1. BigInt operator + (const BigInt &a, const int &b)
2. {
3.   BigInt res = a;
4.   int pos = 0;
5.   res.digits[0] += b;
6.   while (res.digits[pos]>=osn)
7.   {
8.     res.digits[pos+1]++;
9.     res.digits[pos++]-=osn;
10.   }
11.   if (res.digits[res.amount])
12.     res.amount++;
13.   return res;
14. }

* This source code was highlighted with Source Code Highlighter.

Практически идентичную реализацию имеет и операция “длинное – короткое”.

Вывод длинных чисел

[Вся длинная арифметика]
Вывод длинных чисел тесно связан с вводом). Опять же рассмотрим два случая для osn = 10 и для osn = 10000.

Первый случай:

1. void output()
2. {
3.   for (int i=amount-1;i>=0;i--)
4.     cout<<digits[i];
5. }

* This source code was highlighted with Source Code Highlighter.

Второй случай:

1. int len = 4;
2. const char * digitFormat = "%.4d";
3. ...
4. void output()
5. {
6.   printf("%d",digits[amount-1]);
7.   for (int i= amount-2;i>=0;i--)
8.     printf(digitFormat,digits[i]);
9. }

* This source code was highlighted with Source Code Highlighter.

Отметим важный факт во втором случае. Дело в том, что цифра при osn = 10000 может оказаться не четырехзначной. В таком случае нужно побеспокоиться, чтобы она выводилась с лидирующими нулями. Это не касается первой цифры, поэтому ее вывод реализован отдельно

Ввод длинных чисел

[Вся длинная арифметика]

Рассмотрим два случая считывания длинных чисел. Первый случай(базовый), при котором osn = 10. Во втором, в качестве osn выберем одну из степеней десятки. Забегая вперед отмечу факт, что эту степень нужно выбирать очень аккуратно, чтобы избежать переполнения при реализации операций. Так например, если цифра длинного числа хранится в int’е и мы реализуем операцию плюс, то максимально возможная степень десятки у osn будет 9. (В умных книжках обычно после подобных фраз пишут: “Почему?”). Если же реализуем операцию умножения длинного на длинное, то максимальный osn = 1e4. С учетом всего вышесказанного давайте ознакомимся с возможной реализацией первого случая:

Бинарный поиск (binary_search, lower_bound, upper_bound)

binary_search
Формулировка задачи: Узнать, находится ли данный элемент в отсортированном массиве подобных элементов, для которых задано отношение порядка на множестве. Т.е. имея в наличии два элемента, можно однозначно определить операцию <. Сложность O(log(N)).
Реализация:

1. bool binary_search(const vector<int> &mas, const int &value)
2. {
3.   int l = 0, r = mas.size()-1;
4.   while (l<r)
5.   {
6.     int m = (l+r)>>1;
7.     if (mas[m] < value)
8.       l = m +1;
9.     else if (mas[m] > value)
10.       r = m - 1;
11.     else
12.       return true;
13.   }
14.   return mas[l] == value;
15. }

* This source code was highlighted with Source Code Highlighter.

Длинное + длинное

[Вся длинная арифметика]

Операция сложения двух длинных чисел:

1. BigInt operator + (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   res.amount = max(a.amount,b.amount);
5.   int r = 0;
6.   for (int i=0;i<res.amount | r;i++)
7.   {
8.     res.digits[i] = a.digits[i] + b.digits[i] + r;
9.     if (res.digits[i]>=osn)
10.     {
11.       res.digits[i]-=osn;
12.       r = 1;
13.     }
14.     else
15.       r = 0;
16.   }
17.   if (res.digits[res.amount])
18.     res.amount++; 
19.  
20.   return res;
21. }

* This source code was highlighted with Source Code Highlighter.

В данной реализации отсутствует операция взятия остатка от деления. Вместо этого используется вычитание значения основания системы счисления в строке 11.

P.S: Данная реализация появилась на основе статьи Виталия Гольдштейна с учетом оформления длинных чисел команды HotFinnKeys.

Предисловие [Длинная арифметика]

[Вся длинная арифметика] 

Итак мы начинаем разговор о длинной арифметике.
Под длинной арифметикой мы, как и все, будем понимать математические действия над числами, которые по своему размеру превышают ограничения стандартных типов данных. Так например в тип int(4 байта) уместиться число 2^31 = 2147483648 (~2e9), в unsigned int(те же 4 байта) – число 2^32 = 4294967296 (~4e9). В переменную типа long long или __int64(8 байт) “влезет” 2^63 = 9223372036854775808 (~9e18), в безнаковый тип в два раза больше (~1e19). Как мы видим, уже для чисел в 25 разрядов в десятичной системе счисления нет типа в 32 разрядной системе, который бы удовлетворял нашим нуждам. Как быть? Ведь на практике встречаются числа с куда большим количеством разрядов. Унывать не стоит! Предки уже решили эту проблему за нас. Нам остается просто научиться делать тоже самое и не изобретать велосипед. Хотя крайне полезно сперва его изобрести и попытаться самостоятельно решить возникшие в результате проблемы.

Длинная арифметика

Теория:
* Первая глава книги Окулова “Программирование в алгоритмах”.
* Раздел 4 Дистанционная подготовка по информатике
* e-maxx

Практика: Дистанционная подготовка

Условные обозначения:
* osn – основание системы счисления 
* A,B – “длинные” числа
* n – “короткое”, 0 <= n < osn

Предисловие
Основные операции:
* Ввод
* Вывод 
* A + n
* Сравнение
* A + B
* A – B (A >= B)
* A – B (со знаком)
* A * n
* A * B
* A / n, A % n 
* A / B, A % B

Дополнительные операции:
* A^n
* n!
* sqrt(A)
* N^N mod 10^P

Экзотика:
* A – n

Тренировка #4 [Меньшиков]

[Условия задач]                   [Список тренировок] 

4A. Совершенные числа
[perfect]
Хорошая несложная задача. Есть один подвох, на который натыкаются многие. Желаю наткнуться на него всем начинающим, чтобы глубже проникнуться задачей. 
4B. Разложение на слагаемые
[decomp]
Компактная рекурсивная реализация. В ходе решения встает только одна проблема: как не генерировать комбинации слагаемых, которые уже были до этого? Для этого, по рекомендации Меньшикова, условимся, что в получаемой комбинации предыдущее слагаемое не превышает текущего. Этим приемом можно пользоваться и в других подобных задачах для обеспечения уникальности последовательностей.

Тренировка #3 [Меньшиков]

[Условия задач]                   [Список тренировок]

3A.Разложение на простые множители
[pfactor] Типовая соптимизированная реализация
Оптимизация заключается в пересчете верхней границы цикла(корень квадратный из N) при переходе к новому делителю.
3B.Перестановки(2)
[permut2] Рекурсивная реализация с подсчетом элементов
Реализация основана на разборе этой задачи из книги Меньшикова. Первоначально подсчитываем количество вхождений символов из первоначальной перестановки. Затем на i-ое место текущей перестановки ставим ближайший в лексикографическом порядке символ, счетчик которого имеет ненулевое значение, и декрементируем счетчик на единицу.
[permut2] Идентично [permut] next_permutation
Важный факт того, что генерация алгоритмом next_permutation не зависит от того есть ли дублирующие символы во входном наборе или нет. Общий вывод: любая корректная реализация задачи 3B пройдет на задаче 2B.