Занятие №2. Битовые операции и структуры данных

Теория: Лекция                                             [Все занятия]

В очень компактной форме было затронуто большое количество тем.
Очень понравилась реализация битового вектора и механизм отыскания элемента массива, встречающегося нечетное количество раз =)

Практика:                                         [Официальная страница]
Учебные задачи: 
   Задача A.
   [Стек неограниченного размера] 
   Полезная задача. Т.к в условии сказано, что стек потенциально может занимать всю оперативную память, то лучшего его делать на основе односвязного списка, чтобы не получить RE на первых посылках. Но эта реализация будет расходовать в 3 раза больше памяти. Чтобы минимизировать расходы на память удачным решением является односвязный список массивов.
   Задача B.
   [Очередь неограниченного размера]
   Не менее полезная задача. Здесь дело приходится иметь уже с двусвязным списком. Необходимо внимательно рассмотреть случай, когда очередь становится пустой и возникает команда push.
   Задача С.
   [2^n+2^m]
   Задача на базовое понимание битовой арифметики. 
Олимпиадные задачи: 
   Задача A.
   [Забавная игра]
   Несложная задача. Нужно постараться сделать ее, не раскладывая число в двоичное представление. 
   Задача B.
   [Сортировка вагонов]
   Задача на понимание работы стека и умение его использовать в нестандартных ситуациях. Решение имеет сложность O(N). Во время решения пришла идея на проверку возможности сортировки входных данных предложенным способом, основанная на дереве Фенвика. Но в этом случае сложность становится O(NlogN), что делают эту идею бесперспективной на будущее. 
   Задача С.
   [Тупики]
   Шикарная задача на кучи. Из-за того, что по условию лошадиные размеры массивов, и то что они объявлены не глобально пришлось расширять размер системного стека. В реализации используется самописная структура данных “Куча” для int’ов(а надо было основанную на шаблонах), но по ходу решения еще нужно было использовать кучу для пары элементов, поэтому для них использовался STL аналог кучи priority_queue, который работает несколько медленнее рукописного варианта. Но как видим самописная куча и priority_queue имеют одинаковый набор функций + одинаковую сложность функций.
Дополнительные олимпиадные задачи:
   Задача A.
   [Strategy tetris] 2009 Edition
   [Strategy tetris] 2011 Edition
   Еще одна очень хорошая задача на применение кучи. Здесь привожу два решения, потому что показалось, что решение 2009 года получилось понятней =). Обрабатываем фигуры в порядке возрастания значения левой границы. На каждой итерации пытаемся вставить фигуру на такой уровень, на котором правая граница самого правого элемента меньше левой границы текущей фигуры. Если такого сделать не получается, то формируем новый уровень.
   Задача B.
   [Конвейер]
   Повторение – мать учения. Немного усложненный вариант задачи “B. Сортировка вагонов”. В сущности можно обойтись одним стеком + грамотно реализовать сравнение даблов. 
   Задача С.
   [Трехмерные ладьи]
   Хорошая такая задача. Правда далась она мне тяжеловато. Для начала нужно свести куб к трем проекциям: XY, YZ, XZ. Сами проекции можно представить в виде матриц размером N*N. Если имеем ладью с координатами a,b,c, тогда метим прямые XY[a][b], YZ[b][c], XZ[a][c], как прямые, не содержащие ответ на задачу. Тогда задача сводится к нахождению коэффициентов x,y,z таких что XY[x][y] == YZ[y][z] == XZ[x][z] == false (не помеченных). При таком раскладе получаем кубическое решение, которое не зайдет по времени.
Следует модерниризировать матрицы таким образом:
bool XY[N][N]
int  YZ[N][N/32]
int  XZ[N][N/32].
При таком раскладе мы можем при фиксированных x и y быстрее находить нужный z, а именно обрабатывать группу из 32 элементов, прибегнув к битовой арифметике.
Значение YZ[y][z] | XZ[x][z] в двоичном представлении должно состоять только из единиц. Если же это не так и XY[x][y] == false, значит мы нашли клетку, которая не бьется.

Занятие №1. Арифметика и теория чисел [Густокашин]

Теория: Лекция                                                  [Все занятия]

Лекция является вводной, но все равно много интересного можно оттуда почерпнуть. В частности:
1) Нахождения НОД’а длинных чисел на основе формул:
gcd(2a, 2b)     = 2gcd(a,b)
gcd(2a, 2b+1)   = gcd(a,2b+1)
gcd(2a+1, 2b+1) = gcd(2(a-b),2b+1)
Хорошие формулы, уменьшающие накладные расходы. Осталось их только запомнить =)

2) Умножение двух матриц с предварительным транспонированием второй.

Практика:                                              [Официальная страница]
Учебные задачи
  Задача A. 
   [A-B]
   Такие задачи мы уже решали раньше в рамках темы Длинная арифметика.
   Задача B.
   [Целые точки отрезка]
   Если отрезок не параллелен осям координат, то достраиваем его до прямоугольного треугольника, где этот отрезок является гипотенузой, а катеты параллельны осям координат. После чего можно выйти на следующую формулу:
gcd(A,B) + 1, где A и B катеты прямоугольного треугольника. Стоит отметить тот факт, что формула работает и в том случае, если отрезок параллелен любой из оси координат.
   Задача С.
   [Разложение на простые]
   Сложность O(sqrt(N)). Можно смело ввести одну оптимизацию. Стоит заметить, что в строке 34 каждый раз пересчитывается верхняя граница внешнего цикла.
Олимпиадные задачи
  Задача А. 
   [Представление чисел]
   Рассуждаем. N = A + B. При этом нужно максимизировать gcd(A,B). 
A = a * gcd(A,B) 
B = b * gcd(A,B)
=> N = gcd(A,B) * (a + b). Главный вывод в том, что N делится на gcd(A,B) без остатка. Если мы хотим максимизировать gcd(A,B), зная N, то необходимо мизировать (a+b). Следовательно (a+b) – минимальный множитель N, отличный от 1.
Неплохо =). Теперь мы можем найти максимальный gcd(A,B) для любого N. Подумаем как найти сами числа A и B. A = a * gcd(A,B); B = b * gcd(A,B). Но мы не знаем a и b, а знаем только их сумму. Какие же a и b нужно выбрать? Думаем.
Ответ: любые натуральные.
Обратимся к примерам: 
    1) N = 16. a + b = 2. gcd(A,B) = 8. Следовательно a = 1 и b = 1, поэтому A и B определяются однозначно.
    2) N = 35. a + b = 5. gcd(A,B) = 7. Здесь может быть несколько случаев:
a = 1, b = 4;
a = 2, b = 3;
a = 3, b = 2;
a = 4, b = 1;
Понятно, что последние два случая являются зеркальным отображением первых двух, поэтому можно рассматривать только первые два случая. Как видно не важно какой из них мы выберем в качестве ответа. Для того, чтобы не плодить лишние if’ы можно a всегда брать 1. 
    3) N = 17. a + b = 17. gcd(A,B) = 1. В данном случае можно брать любое разложение числа N на слогаемые.
   Задача В.
   [Кинотеатр]
   Судя по ограничениям обычное моделирование ситуации не канает. Начинаем думать. Ко мне решение пришло, когда я нарисовал оба случая для случая n=5,m=7. После чего появились следующие выводы:
1)  Все элементы, которые останутся на своих местах будут находится на виртуальной главной диагонали матрицы.
2) Задача сводится к задаче B из первого блока учебных задач.
   Задача С.
   [Степень]
   Для начала разобьем исходное число А на простые множители в формате, представленном в лекции. Например число 12:
osn  = {2,3}
step = {2,1}, т.е. 12 = 2^2 + 3^1.
Очевидно, что каждый просто множитель из числа A должен входить как минимум один раз в число N. Но не факт, что получившееся число N будет удовлетворять требованиям задачи. Например для такого числа A:
osn  = {2,3}
step = {19,1}
Как быть? Необходимо увеличить число N в минимальное число раз, так чтобы оно удовлетворяло условию задачи.
Дополнительные олимпиадные задачи
   Задача А.
   [Марсианские факториалы]
   Для решения этой задачи сначала можно рассмотреть более простой случай. Будем искать ответ пока только для основания системы счисления = 10. Понятно, что ноль в конце факториала получится, если в разложении факториала на простые множители найдутся 2 и 5. При этом общее количество нулей будет равно количеству 5-ок в разложении факториала на простые множители.
Рассмотрим пример: N = 128. Сколько нулей будет в конце N! ?
Переберем все числа кратные 5, которые не превышают N:
5, 10, 15, 20, 25, 30, … , 120, 125 – всего N/5.
Как можно заметить в этом ряду есть числа, которые в своем разложении имеют несколько 5. Найдем все числа, которые имеют в своем разложении две пятерки:
25, 50, 75, 100, 125 – всего N/25.
Затем найдем числа, которые имеют 3 пятерки в своем разложении:
125 – всего N/125
Сложив количество элементов в этих трех рядах, мы найдем ответ на поставленный вопрос.
Как быть в случае, когда основания системы счисления отлична от 10. 0 в конце числа появится, если в его разложении на простые множители найдутся все простые множители из разложения основания системы счисления. Так например для основания 6(2*3) число 100! будет иметь 48 нулей, потому что 100! содержит 97 двоек и 48 троек. Все вычисления можно проводить в 10-ой системе счисления.
Тонким моментом является ситуация, когда основание системы счисления в своем разложении имеет несколько одинаковых множителей. Например найдем 1000! для osn = 72 = (2^3 * 3^2)
В разложении 1000! имеется 994 двойки и 498 троек. Количество же нулей в конце будет 249.
   Задача В.
   [Скорая помощь]
   Задача на углубленное понимание операций целочисленного деления и взятия остатка от деления. Перебираем количество квартир(от 1 до 1000) на одном этаже и в совокупности с параметрами K2,P2 и N2 определяем корректность перебираемого значения. Если после перебора выяснится, что только одно значение количества этажей являлось корректным, то значит входные данные оказались непротиворечивыми. Т.е. параметры N1 и P1 определяются однозначно. Если же не удалось подобрать количество квартир на одном этаже, либо N2>M, то значит решений нет. Если в качестве количества квартир на одном этаже подошло более одного значения, тогда определяем насколько однозначно можно определить параметры N1 и P1, согласно условию задачи.
   Задача С.
   [Проверьте равенство]
   Кромоздкая задача, в которой помимо того, что нужно реализовывать длинную арифметику, так еще и учесть целую череду частных случаев. Особое внимание к:
0^0 и 0^-1. В решении можно реализовать деление длинного на длинное, а можно этого не делать, если немного подумать.

Очно-заочный кружок [Михаил Густокашин]

Начинаем плавное и методичное прорешивание задач из этого сборника. Стоит отметить качественную подборку задач по тематикам и уровню сложности. Материалы кружка доступны на сайте informatics.mccme.ru.

Занятие №1. Арифметика и теория чисел                          [20Apr2011]
Занятие №2. Битовые операции и структуры данных                [15May2011]
Занятие №3. Алгоритмы поиска в олимпиадных задачах             [22Sep2011] 
Занятие №4. Алгоритмы сортировки                               [25Sep2011]
Занятие №5. STL                                                [03Oct2011]
Занятие №6. Задачи на анализ таблиц                            [14Oct2011]
Занятие №7. ДП с одним параметром                              [23Oct2011]
Занятие №8. ДП с двумя и более параметрами                     [28Oct2011]
Занятие №9. Методы тестирования задач                          [01Nov2011]

P.S: Очень надеюсь, что список тренировок будет продолжен =)

Танцующие звенья (Dancing Links)

Данный алгоритм решает задачу полного покрытия (cover).

Для начала можно ознакомится со следующими статьями:
- Реализация на С и описание (Xi Chen)
- Разжованное описание + базовые операции с элементами списка

В общем случае задача полного покрытия выглядит так:
Имеется набор битовых строк

A[0] = 100101
A[1] = 101000
A[2] = 011011

Необходимо выделить набор, состоящий из одной или нескольких исходных битовых строк, такой что после операции логического ИЛИ всех элементов этого набора, получилась единичная битовая строка. Т.е. в примере набор может состоять из элементов A[0] и A[1].

Рассмотрим применения алгоритм Dancing Links отностительно решения Судоку.

Итак задача формулируется следующим образом:
1) Имеется квадратное поле размером 9 на 9 (81 клетка). В каждой клетке находится цифра в интервале [1,9]
2) В каждой строке не должно быть повторяющихся цифр.
3) В каждом столбце не должно быть повторяющихся цифр.
4) В каждом блоке (см. рисунок) не должно быть повторяющихся цифр.

Задача расставить недостающие цифры так, чтобы выполнялись вышестоящие 4 правила. 

Сведем задачу решения судоку к задаче решения полного покрытия.
Для этого давайте рассмотрим судоку 4 на 4 с аналогичными правилами.

Рассмотрим таблицу №1, которая прояснит момент получения битовых строк для задачи полного покрытия.
Строки матрицы – это кандидаты на решение (вспоминаем общую формулировку задачи полного покрытия)
Столбцы матрицы – это требования к решению.

На каждую клетку можно поставить любое значение в интервале [1,9], т.е. получается всего N*N*N возможных решений.

Разберемся теперь с требованиями. Всего существует 4 вида требований:
1. Каждая строка должна  иметь все числа от 1..N = N * N требования
2. Каждый столбец должен иметь все числа от 1..N = N * N требования
3. Каждый квадрат должен иметь все числа от 1..N = N * N требования
4. Каждая клетка судоку должна иметь уникальное значение в интервале от 1..n. Другими словами если в клетке [i,j] находится число k, то нужно исключить из рассмотрения оставшиеся N-1 значения не равные k = N * N требования

Таким образом мы имеем 4*N*N требований.

Для случая 4*4 имеем матрицу размерностью [64 на 64]. Теперь вникаем в суть как заполняется матрица. Это можно сделать самостоятельно последовательно рассмотрев все строки сверху вниз.

Допустим начальная расстановка такая:

1---
----
----
----

Чтобы это отразилось на рассматриваемой матрице необходимо найти строку(0) решения, которая соответствует введенному значению.
Затем необходимо выполнить операцию Cover. А именно занулить эту строку + все столбцы, которые пересекает данная строка + все строки, которые пересекают столбцы. Чтобы понять эту игру слов анализируем таблицу №2.

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

Если присмотреться к матрице, то можно заметить, что в каждой строке и столбце находится N единиц. Поэтому следующей нашей задачей будет формирования сжатой копии матрицы в виде, представленном выше. Это дело техники, поэтому не будем останавливаться на этом подробно. Отмечу только один факт, что для отладки я немного модернизировал вывод матрицы, добавив в него вывод последних трех цифр адреса узла в памяти. Смотрим таблицу №3.

Теперь сформулируем процесс нахождения решения.
1. Последовательно перебираем требования начиная с root. Если на текущем шаге не осталось требований, значит нужно проверить получившееся решение на корректность.
2. Для каждого требования пытаемся использовать строку-решение, с которой пересекается данный столбец.
3. Для каждой такой строки выполняем операцию Cover, тем самым исключая не нужные элементы из последующего рассмотрения.
4. Рекурсивно переходим в новое состояние – новое требование.
5. (После выхода из рекурсии) восстанавливаем состояние до вызова функции Cover и пытаемся использоваться следующее решение.

Как можно заметить вышеописанный алгоритм не что иное как Backtracking. Но в отличии от обычного, здесь нахождение следующего корректного кандидата составляет O(1) вместо O(N). Операция Cover и обратная ей также выполняется за O(1). Тем самым обеспечивается быстрота, заявленная в начале поста.

Мои наработки находится в этом исходнике.

P.S.: Вообще взялся за этот алгоритм с одной целью. Зачесть задачу, в которой нужно собрать судоку 16*16. Но как показала практика, DLX(Dancing Links) в том виде, в котором он изложен здесь, работает недостаточно шустро. Если у кого есть идеи по решению этой задачи, будет интересно услышать.