Тренировка #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)