Занятие №6. Задачи на анализ таблиц.

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

Практика:                                 [Официальная страница]

Учебные задачи:
   Задача А.
   [Побочная диагональ]
Хорошая незатейливая задача =) 
   Задача В.
   [Шахматная доска]
Т.к. изначально сказано, что область является связной, то нет необходимости писать поиск в глубину(лишний расход памяти на рекурсию) или поиск в ширину(просто дольше писать). Достаточно перебрать 64 клетки поля и определить периметр, просмотрев все соседние клетки. В этой задаче не лишним будет обнести всё поле границей фиктивными клетками, чтобы не писать дополнительные проверки на выход за пределы шахматной доски.
   Задача С.
   [Поворот]
Если бы требовалось в результате программы получить матрицу, то предложенное решение требует дополнительно O(N*N) памяти. Можно придумать решение, в котором все манипуляции происходят на исходной матрице. Для этого вычленяем 4 угловые клетки и делаем их циклический сдвиг. Последовательно перебираем все возможные такие четверки и получаем ответ. Учитывая небольшие ограничения, данное решение не приводится.
Олимпиадные задачи:
  Задача А.
   [Сапер]
Классика жанра. Опять же очень удачной мыслью будет обнести поле фиктивными клетками, чтобы отдельно не проверять случай выхода за границы поля. 
  Задача В.
   [Игра с фишками]
Очень хорошая задача, чтобы попрактиковаться в реализации BFS на таблицах. В данной задаче я не обносил матрицу фиктивными элементами. Вместо этого использовалась функция correct(int x, int y) для проверки выхода за пределы игрового поля. 
   Задача С.
   [Вырезание фигуры]
Можно хранить всю матрицу целиком, а связные области находить BFS’ом. Но можно поступить более изящно. Можно искать углы фигуры. По условию сказано, что фигуры не пересекаются и не соприкасаются углами или сторонами, следовательно можно выделить двоичные маски углов, а именно:
0|1   1|0   1 1    1 1
1 1   1 1   0|1    1|0   - являются битовыми масками внешних углов(OUT) вырезанной фигуры.

также существуют внутренние углы(IN) фигуры. Битовые маски внутренних углов фигуры получаются инверсией битовых масок внешних углов. Показателен тот факт, что для любой вырезанной фигуры верна формула: OUT – IN = 4.
Дополнительные олимпиадные задачи:
  Задача А.
   [Восстанови многоугольник]
Лучше разбор наверное не придумать: [Автор: Владимир Гуровиц]
   Задача В.
   [Электронные часы]
Казалось бы несложная задача. Но здесь есть пара подводных камней. В частности количество часов может получиться больше 23, а количество минут больше 59. Эти две ситуации нужно корректно обработать. Я это сделал таким образом:
1) 4 списка возможных значений на каждое цифровое поле часов.
2) Получил все возможные комбинации часов перебрав все допустимые пары первой и второй цифры.
3) Получил все возможные комбинации минут перебрав все допустимые пары третьей и четвертой цифры
4) Отсеял все невалидные значения часов и минут.
Если хотя бы один из списков пуст, значит произошла ошибка. Выводим ERROR
Если хотя бы в одном списке больше 1 элемента, значит возможна двоякая интерпретация. Выводим AMBIGUITY.
В противном случае в каждом списке по одному элементу, т.е. удалось однозначно установить время. Выводим его. B здесь нас ждет еще один подводный камень. Нужно не забыть про ведущие нули.
   Задача С.
   [Историки и археологи]
Если присмотреться, то можно заметить, что процедура переселения представляет собой обычное транспонирование подматрицы. В результате чего происходит реверс элементов относительно главной диагонали. Вот собственно и на этом будет строиться наше решение. Для начала условимся, что будем приводить первую матрицу ко второй последовательно, подиагонально. Диагонали будем перебирать слева-направо, сверху-вниз, т.е. первая диагональ будет состоять из одного элемент (0,0), вторая диагональ из двух – (1,0) и (1,0) и т.д. Транспонирование нужно выполнять осторожно. Если в качестве подматрицы выбрать матрицу размером большим, чем 2*2, то произойдут обмены элементов прошедших и уже упорядоченных диагоналей. Поэтому в качестве подматрицы будем использовать только матрицы размером 2*2. А транспонирование подматрицы будет идентично реверсу побочной диагонали, или обмену двух соседних элементов текущей диагонали. При упорядочивании диагонали будем использовать принцип аналогичный сортировки пузырьком.

Обратное индексирование или обнуление массива за O(1)

В общем виде задача формулируется так:

Нужно создать структуру данных поддерживающую 3 вида операций на массиве:
1) set(i,value) – инициализация i-ого элемента значением value
2) get(i) – получение значение i-ого элемента
3) clear() – обнуление массива.

Каждая операция должна выполняться за O(1).

Первое, что мне пришло в голову было это:

1. struct ARRAY {
2.   vector<int> val;
3.   vector<int> met;
4.   int cur;
5.   int lastClear;
6.   ARRAY():cur(0), lastClear(0){}
7.   ARRAY(int size):cur(0), lastClear(0) {
8.     val.resize(size,0);
9.     met.resize(size,0);
10.   }
11.   void set(int pos, int value) {
12.     val[pos] = value;
13.     met[pos] = ++cur;
14.   }
15.   int get(int pos) {
16.     if (met[pos] > lastClear)
17.       return val[pos];
18.     return 0;
19.   }
20.   void clear() {
21.     lastClear = ++cur;
22.   }
23. };

* This source code was highlighted with Source Code Highlighter.

Но как это все уж больно по-пацаняче. С более изящным решением меня познакомил Кирилл Цыганов. Оно основано на принципе обратного индексирования:

1. const int MAX_REQ = 1000; // максимальное количество запросов set между вызовами clear
2. struct ARRAY {
3.   vector<int> A; // key - индекс; val - значение
4.   vector<int> S; //key - порядковый номер элемента при добавлении; val - индекс элемента в A
5.   vector<int> ID;//key - индекс элемента в A; val - порядковый номер элемента при добавлении
6.   int amount;
7.   ARRAY():amount(1){}
8.   ARRAY(int N):amount(1) {
9.     A.resize(N);
10.     S.resize(MAX_REQ);
11.     ID.resize(MAX_REQ);
12.   }
13.   void set(int pos, int value) {
14.     A[pos] = value;
15.     S[amount] = pos;
16.     ID[pos] = amount++;
17.   }
18.   int get(int pos) {
19.     if (ID[pos] > amount) // попали в мусор (после clear)
20.       return 0;
21.     if (S[ID[pos]] != pos) // обращение к неинициализированному элементу
22.       return 0;
23.     return A[S[ID[pos]]];
24.   }
25.   void clear() {
26.     amount = 0;
27.   }
28. };

* This source code was highlighted with Source Code Highlighter.

Занятие №5. STL

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

Практика:                                                [Официальная страница]

Учебные задачи:
   Задача A.
   [Сортировка]
На этой задаче можно тестировать корректность работы “быстрых” сортировок.
   Задача B.
   [Хеширование с удалением]
На момент 26Sep2011 15:59 данная реализация получала RE на 8 тесте. Верное решение 2-х летней давности получала тот же вердикт. Проблема связана с нехваткой памяти, вызванное переходом на 64 битную версию линукса, стоящего на сервере проверяющей системы. 
Эту задачу можно сдать с текущими ограничениями с помощью хеширования(алгоритм Рабина-Карпа) или с помощью построения дерева(алгоритм Ахо-Корасик), но т.к. данная задача предусматривалась в рамках учебных задач на STL, то условимся, что решение с использованием set нас полностью устраивает.
   Задача С. 
   [Двоичный поиск]
А на этой задаче можно тестировать рукописную дихотомию.
Олимпиадные задачи:
   Задача A.
   [Сплоченная команда]
Решение получилось прям очень STL’вским) Сначала сортируем игроком по их ПП. Далее последовательно перебираем пары двух игроков G1 и G2, стоящих рядом. Сумма их ПП определяет значение ПП максимального игрока G3 в команде. G3<=G1+G2. Чтобы найти позицию игрока G3 максимально удовлетворяющему игрокам G1 и G2 можно воспользоваться функцией upper_bound на отсортированном массиве игроков. Чтобы найти сумму игроков в команде за O(1), можно заранее сделать подсчет интервальных подсумм. 
   Задача B.
   [Древние цивилизации] Ответ за O(NlogN): multiset
Написал небольшого монстрика, который сильно перегружен STL. Но зато я впервые попользовался обратными итераторами (reverse_iterator). Восстановление ответа использует multiset. Это связано с компаратором. На самом деле основная идея лучше реализована в исходнике двух летней давности, который находится ниже. Там восстановление ответа написано тоже за O(NlogN), но константа будет меньше. Этот исходник выкладываю исключительно для себя, чтобы в следующий раз такого не делать).
   [Древние цивилизации] Ответ за O(N)
Самая адекватная реализации данной задачи. Очередной пример того, что не надо нагружать программу красивыми фенечками, вместо того, чтобы немного подумать. Можно заметить, что нужный интервал будет образовываться между двумя соседними историческими событиями. Под историческим событием я понимаю либо зарождение, либо гибель одной из цивилизаций. При этом левой границей интервала будет зарождение, а правой – гибель цивилизации. Крайний случай будет если нужный интервал совпадает с периодом одной из цивилизации (назовем ее цивилизации A). В крайнем случае нужно найти вторую цивилизацию, которая существовала до цивилизации A а погибла после. Это можно сделать за O(N).
   [Древние цивилизации] Ответ за O(NlogN): set [25Nov2009]
Данное решение выкладываю тоже исключительно для себя. Логарифм в сложности вылезает из-за крайнего случая, описанного во втором решении. Я пытался сразу обрабатывать крайний случай для поиска второй цивилизации. Это приводило к тому, что все зародившиеся множества клались в множество, а при гибели они из этого множества удалялись. Как известно каждая операция выполняется за O(logN).
   Задача С.
   [Число]
Идентичная задача была на ACM ICPC Subregional Contest 2007 в Саратове. Вот она на сервере acm.sgu.ru. Приятно вспомнить, что тогда мы ее зачли). Спасибо Роману и Рамилю. 
Дополнительные олимпиадные задачи:
   Задача A.
   [Современники]
Задача на сканирующую линию. Создаем массив из дат. Для каждой даты храним метку, является ли она началом периода или концом. В качестве даты нужно добавлять день [18-летия](начало) и день [80-летия – 1 день](конец). Небольшая сложность состоит в подсчете даты [80-летия – 1 день]. Для этого нужно аккуратно выписать количество дней в месяцах и не забыть обработать случай високосного года.
   Задача B.
   [Контрольная по ударениям]
Задача на быстрое нахождение слова в словаре. По ходу решения удобно завести два множества. В первом будем хранить слова с ударением, а во втором – те же слова в нижнем регистре для определения наличия слова без проверки на ударение.
   Задача С.
   [Умный чертежник] Сложное решение =)
По условию задачи робот не может проехать по нарисованной ранее линии. Можно представить перемещения работа в виде графа. Этот граф будет представлен либо Эйлеровым путем, либо Эйлеровым циклом(справка). Следовательно либо все степени вершин графа являются четными(Эйлеров цикл), либо 2 вершины имеют нечетную степень,а все остальные четную(Эйлеров путь). Также отметим, что граф является связным. Суть данного решения заключается в том, что мы двигаемся по исходному графу как захотим. Во время движения не меняем направления только в том случае, если этого сделать нельзя. Т.е. избегаем комбинаций в маршруте типа “EE”, “WWW” и подобных, если это возможно. Такая тактика приведет к тому, что все вершины с нечетными степенями будут содержаться в нашем пути. Но может возникнуть ситуация, когда некоторые вершины будут не использованы в маршруте. Неиспользованные вершины будут образовывать конечное количество циклов. Чтобы все неиспользованные циклы добавить в ответ нужно найти место в ответе, куда нужно их вставить. Эту операцию можно сделать путем пересечения множеств использованных и неиспользованных вершин. Вершина считается использованной, если не осталось неиспользованных ребер, исходящих из нее. Поясним более наглядно вышесказанное.
Исходный путь: NNWSEE
Первоначальный путь: NE
В результате остался неиспользованный цикл WNES. Его нужно вставить после первого шага. В итоге получаем ответ: NWNESE
   [Умный чертежник] Простое решение !
Предыдущее решение было не очень продуманным в плане простоты реализации. Если подумать, можно заметить, что если робот наткнулся на самопересечение в точке P, то нужно двигаться в обратную сторону между двумя попаданиями в точку P в рамках первоначального пути. Важно учесть, что после такого “реверса” пути заново пройти весь путь с первоначального попадания в точку P, чтобы проверить наличие самопересечений последующего пути с “реверснутым” подпутем.

Поразрядная сортировка (Radix_sort)

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

Теория: Wikipedia

Практика: acmp.ru

Реализация:

Условимся, что мы обрабатываем только массив неотрицательных целых чисел.

Первая реализация обрабатывает разряды десятичного числа начиная с младших. Количество разрядов в числе задается в константе RADIX_AMOUNT.

1. typedef unsigned int UINT;
2. . . .
3. void radix_sort10(UINT* &a, int size) {
4.   UINT* b = new UINT[size];
5.   UINT* title = new UINT[10];
6.   UINT* count = new UINT[10];
7.   UINT* prev = new UINT[size];
8.  
9.   memset(count,0,sizeof(UINT) * 10);
10.   char curDig;
11.   int osn = 10;
12.   int del = 1;
13.   for (int r=0;r<RADIX_AMOUNT;r++) {
14.     for (int i=0;i<size;i++) {
15.       curDig = (a[i] % osn) / del;
16.       prev[i] = title[curDig];
17.       title[curDig] = i;
18.       count[curDig]++;
19.     }
20.     int bPos = size;
21.     for (int i=9;i>=0;i--) {
22.       while (count[i]) {
23.         b[--bPos] = a[title[i]];
24.         title[i] = prev[title[i]];
25.         count[i]--;
26.       }
27.     }
28.     osn *= 10; del *= 10;
29.     swap(a,b);
30.   }
31.   delete[] b;
32.   delete[] title;
33.   delete[] count;
34.   delete[] prev;
35. }

* This source code was highlighted with Source Code Highlighter.

Вторая реализация обрабатывает цифру, состоящую из 8 байт. Т.е. исходное число обрабатывается в системе счисления с основанием 256 и содержит не более 4 цифр.

1. void radix_sort256(UINT* &a, int size) {
2.   UINT* b = new UINT[size];
3.   UINT* title = new UINT[256];
4.   UINT* count = new UINT[256];
5.   UINT* prev = new UINT[size];
6.   UINT mask[4] = {0x000000FF,
7.         0x0000FF00,
8.         0x00FF0000,
9.         0xFF000000};
10.  
11.   memset(count,0,sizeof(UINT) * 256);
12.   unsigned char curDig;
13.   for (int r=0;r<1;r++) {
14.     for (int i=0;i<size;i++) {
15.       curDig = a[i] & mask[r];
16.       prev[i] = title[curDig];
17.       title[curDig] = i;
18.       count[curDig]++;
19.     }
20.     int bPos = size;
21.     for (int i=255;i>=0;i--) {
22.       while (count[i]) {
23.         b[--bPos] = a[title[i]];
24.         title[i] = prev[title[i]];
25.         count[i]--;
26.       }
27.     }
28.     swap(a,b);
29.   }
30.   delete[] b;
31.   delete[] title;
32.   delete[] count;
33.   delete[] prev;
34. }

* This source code was highlighted with Source Code Highlighter.

Сортировка подсчетом (Counting sort)

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

Теория: Wikipedia

Практика: acmp.ru

Реализация:

1. void counting_sort(vector<int> &mas) {
2.   vector<int> amount(MAX_VALUE,0);
3.   for (int i=0;i<mas.size();i++)
4.     amount[mas[i]]++;
5.   int pos = -1;
6.   for (int i=0;i<MAX_VALUE;i++)
7.     for (int j=0;j<amount[i];j++)
8.       mas[++pos] = i;
9. }

* This source code was highlighted with Source Code Highlighter.