понедельник, 29 ноября 2010 г.

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


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

среда, 24 ноября 2010 г.

Тренировка #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, если это возможно.


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

пятница, 19 ноября 2010 г.

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

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

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

среда, 17 ноября 2010 г.

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

Одна из лучших книг по алгоритмам (если не лучшая), которую мне доводилась читать.
Отличная подборка задач по всем предложенным темам. Предлагаемые задачи заставляют мыслить неординарно. По всем задачам есть рекомендации к решению. Ко многим задачами приведены решения на языке 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;

вторник, 16 ноября 2010 г.

Массив [Array]

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

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

понедельник, 15 ноября 2010 г.

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

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

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

пятница, 12 ноября 2010 г.

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

Теория:   Wikipedia, Hardfire

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

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

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