Занятие №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, значит мы нашли клетку, которая не бьется.