среда, 21 декабря 2011 г.

Tim Sort

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

Теория:
habrahabr.ru, код реальных мужиков на С (зеркало)

Практика:
informatics.mccme.ru

Немного размышлений:
1) Не так давно общественность была взбудоражена малоизвестной сортировкой Tim Sort, которая творит чудеса. Поэтому возникло желание попробовать сделать ее реализацию. Когда разбирался в описании, представленном на хабре и в wikipedia, как в русской, так и в английской, возникли вопросы, на которые я не смог найти ответы. Больше всего вызывала вопросов та часть, в которой происходит эффективное слияние подмассивов, примерно равной длины. Т.к. я писал сортировку для случайного набора данных, поэтому хотелось избежать непоняток с волшебными длинами X,Y и Z, а именно просто сливать два последних подмассива, если они имеют одинаковую длину. Как показала практика в оригинальном алгоритме преследовалась та же идея.

Разбираясь в реализации на С(см. теория), было выведено правило грамотного слияния подмассивов с поддержанием баланса длин. Пусть X,Y,Z  - длины верхних трех интервалов, которые лежат в стеке. Причем X – это последний элемент стека.
Правило следующее:
1. Повторяем пока выражение (Z > X + Y && Y > X) не станет истинным
2. Если количество элементов в стеке не меньше 3 и Z <= X + Y – сливаем Y c min(X,Z).
   Иначе Если Y<=X – сливаем X c Y
3. Возвращаемся в п.1.

В wikipedia и на habr’e написано другое правило, в котором X и Z поменены местами, и по которому ничего путного сделать у меня не получилось.

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

3) Для меня осталась загадкой, откуда у автора алгоритма Тима Петерсона такая любовь к сортировке вставками, которая требует в худшем случае n(n-1)/2 обменов. Хотя конечно, для худшего случая, когда массив упорядочен в обратном порядке, стоят нужные механизмы, которые реверснут массив за n/2 обменов, но все равно вопрос для меня остался открытым. В этом плане мне больше импонирует сортировка выбором, которая требует не более n обменов, которая и была приведена в реализации.

Реализация:

  1. struct segment {
  2.   int beg; // индекс первого элемента
  3.   int len; // длина интервала
  4.   segment(){}
  5.   segment(int b, int l) : beg(b), len(l){}
  6. };
  7. // ответ должен быть в диапазоне (32,64]
  8. inline int get_min_size(int n) {
  9.   int r = 0;
  10.   while (n >= 64) {
  11.     n >>= 1;
  12.     r |= n &1;
  13.   }
  14.   return n + r;
  15. }
  16. // Да простит меня Тим Петерсон, но вместо сортировки вставками
  17. // я использую сортировку выбором
  18. void selection_sort(vector<int> &mas, int beg, int last) {
  19.   for (int i=beg; i<last;++i) {
  20.     int min_pos = i;
  21.     for (int j=i+1; j<last; ++j) {
  22.       if (mas[j] < mas[min_pos])
  23.         min_pos = j;
  24.     }
  25.     swap(mas[i],mas[min_pos]);
  26.   }
  27. }
  28. const int dx = 1, dy = 2, dz = 3;
  29. void merge(vector<int> &mas, vector<segment> &seg, bool isXY, vector<int> &tmp) {
  30.   segment f = seg[seg.size() - dy];
  31.   segment s = isXY ? seg[seg.size() - dx] : seg[seg.size() - dz];
  32.   if (f.beg > s.beg) swap(f,s);
  33.   int posF = 0, posS = s.beg, pos = f.beg-1;
  34.   int lstF = f.len, lstS = s.beg + s.len;
  35.   copy(mas.begin() + f.beg + posF, mas.begin() + f.beg + lstF, tmp.begin());
  36.   int fAmount = 0, sAmount = 0;
  37.   while (posF < lstF && posS < lstS) {
  38.     if (tmp[posF] < mas[posS]) {
  39.       mas[++pos] = tmp[posF++];
  40.       ++fAmount; sAmount=0;
  41.       if (fAmount == 7) {
  42.         vector<int>::iterator it = upper_bound(tmp.begin() + posF, tmp.begin() + lstF, mas[posS]);
  43.         copy(tmp.begin() + posF, it, mas.begin() + pos + 1);
  44.         pos += it - (tmp.begin() + posF);
  45.         posF += it - (tmp.begin() + posF);
  46.       }
  47.     }
  48.     else {
  49.       mas[++pos] = mas[posS++];
  50.       fAmount=0; ++sAmount;
  51.       if (sAmount == 7) {
  52.         vector<int>::iterator it = upper_bound(mas.begin() + posS, mas.begin() + lstS, tmp[posF]);
  53.         copy(mas.begin() + posS, it, mas.begin() + pos + 1);
  54.         pos += it - (mas.begin() + posS);
  55.         posS += it - (mas.begin() + posS);
  56.       }
  57.     }
  58.   }
  59.   copy(tmp.begin() + posF, tmp.begin() + lstF, mas.begin() + pos + 1);
  60. }
  61. void try_merge(vector<int> &mas, vector<segment> &seg, vector<int> &tmp, bool is_merge = false) {
  62.   while (seg.size() > 1) {
  63.     int x = seg[seg.size() - dx].len;
  64.     int y = seg.size() < 2 ? 0 : seg[seg.size() - dy].len;
  65.     int z = seg.size() < 3 ? 0 : seg[seg.size() - dz].len;
  66.     if (seg.size() >= 3 && z <= x + y) {
  67.       if (z < x) {
  68.         merge(mas,seg,false,tmp);
  69.         seg[seg.size() - dz].len += seg[seg.size() - dy].len;
  70.         seg[seg.size()- dy] = seg[seg.size()- dx];
  71.         goto POP_BACK;
  72.       }
  73.       else {
  74.         merge(mas,seg,true,tmp);     
  75.         seg[seg.size() - dy].len += seg[seg.size() - dx].len;
  76.         goto POP_BACK;
  77.       }
  78.     }
  79.     else if (is_merge || y <= x) {
  80.       merge(mas,seg,true,tmp);
  81.       seg[seg.size() - dy].len += seg[seg.size() - dx].len;
  82.       goto POP_BACK;
  83.     }
  84.     else
  85.       break;
  86. POP_BACK: seg.pop_back();
  87.   }
  88. }
  89. void tim_sort(vector<int> &mas) {
  90.   int n = mas.size();
  91.   vector<int> tmp(n);
  92.   int min_size = get_min_size(n);
  93.   int beg = 0, size = min_size;
  94.   vector<segment> seg;
  95.   seg.reserve((n-1)/min_size + 1);
  96.  
  97.   for (int i=0;i<n;i+=min_size) {
  98.     size = min(min_size,n-i);
  99.     selection_sort(mas,i,i+size); 
  100.     seg.push_back(segment(i,size));
  101.     try_merge(mas, seg, tmp);
  102.   }
  103.   while (seg.size() != 1) {
  104.     try_merge(mas, seg, tmp, true);
  105.   }
  106. }
* This source code was highlighted with Source Code Highlighter.

P.S: Признаюсь я изначально не возлагал больших надежд на эту сортировку(особенно на свою эффективную реализацию), но должен признать, что был не прав. Данная реализация зашла за 0.061 с, в то время, когда быстрая работал за 0.059 с. Учитывая, что в данную реализацию можно добавить копирование меньшего подмассива + дописать бинарный поиск по не возрастанию, данная сортировка становится пожалуй лучшей для сортировки случайного набора данных. Разработчики Python не могли ошибаться =).

понедельник, 19 декабря 2011 г.

Минимальный циклический сдвиг

Задача: “Дается строка S. Длина S не превышает 1e5. Необходимо найти минимальный в лексикографическом порядке циклический сдвиг строки S”.

1.Полиномиальные хеш-функции.
По мотивам презентации Александра Скиданова

Рассмотрим строку S = “abcdabb”
h(L) – полиномиальная хеш-функция от префикса строки S длины L.




h(0) = h(“”)        = 0
h(1) = h(“a”)       = a
h(2) = h(“ab”)      = a*x1 + b
h(3) = h(“abc”)     = a*x2 + b*x1 + c
h(4) = h(“abcd”)    = a*x3 + b*x2 + c*x1 + d
h(5) = h(“abcda”)   = a*x4 + b*x3 + c*x2 + d*x1 + a
h(5) = h(“abcdab”)  = a*x5 + b*x4 + c*x3 + d*x2 + a*x1 + b
h(5) = h(“abcdabb”) = a*x6 + b*x5 + c*x4 + d*x3 + a*x2 + b*x1 + b

Рекурсивно полиномиальную хеш-функцию h(L) можно выразить так:


H(a,b)- полиномиальная хеш-функция от подстроки S в интервале [a,b)

Следовательно можно получать полиномиальные хеш-функции от любой подстроки S за O(1).

Пусть len – длина строки S.
Возвращаемся к первоначальной задачи. Чтобы найти минимальный циклический сдвиг строки S:
1) Модифицируем исходную строчку S = S + S.
2) Считаем полиномиальную хеш-функцию h(L) для всех префиксов строки S.
3) На текущем шаге наилучший ответ на поставленную задачу – это подстрока строки S длины len, начинающаяся c позиции best = 0.
4) Последовательно перебираем все возможные начальные позиции cur в интервале [1,len)
5) Бинарным поиском подбираем длину общего префикса для наилучшего текущего ответа, начинающегося с позиции best, и кандидата на это место, начинающегося с позиции cur.
6) Сравниваем первые различные символы двух образцов. Если у текущего кандидата на этой позиции стоит символ с меньшим кодом, тогда обновляет наилучший ответ.

  1. typedef unsigned long long UINT;
  2. int min_cycle_shift(char *s, int init_len) {
  3.   UINT *hash = new UINT[2*init_len];
  4.   hash[0] = 0;
  5.   for (int i=1;i<2*init_len;++i)
  6.     hash[i] = x * hash[i-1] + s[i-1];
  7.  
  8.   int bst_pos = 0;
  9.   for (int cur_pos = 1; cur_pos < init_len; ++cur_pos) {
  10.     int l = 0, r = init_len-1, res = 0;
  11.     while (l <= r) {
  12.       int len = (l + r) >> 1;
  13.       UINT hash_bst = hash[bst_pos + len] - hash[bst_pos] * _pow[len];
  14.       UINT hash_cur = hash[cur_pos + len] - hash[cur_pos] * _pow[len];
  15.       if (hash_bst == hash_cur) {
  16.         res = len;
  17.         l = len + 1;
  18.       }
  19.       else {
  20.         r = len - 1;
  21.       }
  22.     }
  23.     if (s[bst_pos + res] > s[cur_pos + res])
  24.       bst_pos = cur_pos;
  25.   }
  26.   delete[] hash;
  27.   return bst_pos + 1;
  28. }
* This source code was highlighted with Source Code Highlighter.

Сложность данного решения:

P.S: В качестве x нужно использовать небольшое простое число. Например 11.
P.S.S: Все вычисления ведутся без модульной арифметики. Поэтому интервал возможных значений полиномиальной хеш-функции равен 264.

2. Алгоритм Дюваля

Все что нужно - написано на e-maxx’e. Приведу просто фрагмент кода, решающую ту же самую задачу.

  1. // s уже равна s+s
  2. int min_cycle_shift(char *s, int len) {
  3.   int i = 0, ans = 0;
  4.   while (i < len/2) {
  5.     ans = i;
  6.     int k = i, j = i+1;
  7.     while (j < len && s[k] <= s[j]) {
  8.       if (s[k] < s[j])
  9.         k = i;
  10.       else
  11.         ++k;
  12.       ++j;
  13.     }
  14.     while (i<=k)
  15.       i += j - k;
  16.   }
  17.   return ans + 1;
  18. }
* This source code was highlighted with Source Code Highlighter.

Сложность данного решения:

понедельник, 12 декабря 2011 г.

Сортировка большого файла с целыми числами: Генератор тестов (Часть 1)

[Все части]
[Прошлая часть: Вводное слово]

Итак, чтобы удобнее было готовится к нашему состязанию, была разработана небольшая утилита для генерации тестов.
При запуске утилиты big_sort_tests_gen.exe мы видим следующую таблицу.

После того, как все настройки выставлены, вводим команду –start.

Общий механизм работы утилиты:
На первом этапе все числа равномерно распределяются между между временными файлами. После чего запускаются независимые потоки, в которых генерируются временные файлы с тем количеством чисел, которые файл получил во время распределения:

На втором этапе все временные файлы сливаются в один:
После выполнения первых двух этапов мы получаем информацию о времени, которое было затрачено на их выполнение:
Корректность сгенерированного файла можно проверить с помощью команды –check:
Если файл сгенерирован, согласно требованиям условия задачи(см. Прошлый пост: Вводное слово), то появится “OK!”. В противном случае будет выведено описание ошибки.

Все сгенерированные файлы записывают в директорию test, расположенную вместе с исполняемым файлом утилиты.

О настройках генератор довольно популярно изложено в следующем видео:

Исходник генератора (проект MS VS 2008, Win32, C++): http://tinyurl.com/cvm6s3a
Бинарники генератора + окружение(Win32): http://tinyurl.com/c9qch5v
Откомпилированный генератор под Linux ждем от Сагунова Данила.

Если у Вас возникли вопросы, предложения, замечания. Будем рады их услышать

Сортировка большого файла с целыми числами: Вводное слово (Часть 0)

[Все части]
[Следующая часть: Генератор тестов]

Не так давно родилась идея организовать небольшое состязание на самое быстрое решение следующей задачи.

Условие задачи:
Входной текстовый файл input.txt содержит набор из N 32-ух битных знаковых чисел, разделенных между собой ровно одним пробелом. Необходимо отсортировать числа из входного файла и записать их во выходной файл output.txt. 1<=N<=1e9.

Регламент:
0. Приглашаются к участию все желающие. Вне зависимости от города проживания и возрастной группы.

1. Решение участника должно быть представлено в виде exe файла, скомпилированного под Windows. Файлы input.txt и output.txt будут находиться в той же директории, что и исполняемый файл. Допускается наличие любых сторонних файлов(библиотеки, конфиги и пр.) вместе и исполняемым файлом.

2. Программа может рассчитывать на:
1) HDD: 10 GB
2) RAM: 128 MB

3. Проверяться решение будет на ноутбуке со следующими параметрами:
1) Процессор: Intel Core2Duo T5250 1.5GHz (Параметры железа могут измениться)
2) Платформа: Windows 7 (x86)
3) Файловая система: NTFS

4. Решение считается зачтенным, если оно успешно прошло все заготовленные тесты и не выкинуло ни одного исключения. На каждом тесте программа будет запускаться 10 раз. Результатом работы программы будет усредненное время. Если программа во время своей работы использовала лишнеее место на жестком диске или лишнюю оперативную память, то оно штрафуется. Зачтенные решения ранжируются по времени работы. Побеждает самое быстрое решение.


5. Решения можно реализовывать на любом языке программирования, использовать любые сторонние библиотеки. Главное, чтобы с исполняемым файлом шел весь набор библиотек. Если будет замечено вредительство со стороны программы: –10 к карме автора решения.

6. Максимальный срок подачи решения 15 января 2012 (Возможно продление этого срока по желанию участников, т.к. в это время будет проходить сессия у студентов и подготовка к областной олимпиаде по информатике у школьников).

Главный приз: 1 Euro и признание со стороны товарищей(бесценно).
По итогу состязания будет разбор общих подходов к решению подобных задач(о нем будет сказано в последующих частях).

Все вопросы и пожелания пишите здесь в комментариях или в группе: http://vkontakte.ru/club13315512

[Следующая часть: Генератор тестов]

Сортировка большого файла с целыми числами

Текущий список участников:
1. Беляев Игорь     (г. Астрахань – АГТУ - аспирант)
2. Бородин Виталий  (г. Астрахань – АГТУ - студент)
3. Елизаров Дмитрий (г. Астрахань – АГТУ - аспирант)
4. Сагунов Данил    (г. Астрахань – АТЛ  - школьник)
5. Степанов Павел   (г. Астрахань – АГТУ - студент)
6. Чаплыгин Андрей  (г. Астрахань - разработчик)

Часть 0: Вводное слово.
Описывается регламент состязания: условие задачи, параметры железа и критерии правильности решения.

Часть 1: Генератор тестов
Представлена утилита, генерирующая тесты, согласно описанной задаче. Можно задавать диапазон генерируемых чисел.

среда, 9 ноября 2011 г.

Фибоначчиева куча(Fibonacci heap)

Литература: Кормен и Co. Алгоритмы. Построение и анализ.
Справочные материалы:
Вики-конспекты ИТМО
Визуализаторы:
rain.ifmo.ru

Крайне любопытная структура данных, на основе которой можно организовать приоритетную очередь.
Ниже представлена асимптотическая сложность базовых операций:

1. Добавление нового элемента          O(1)
2. Определение минимального элемента   O(1)
3. Слияние двух фибоначчиевых куч      O(1)
4. Удаление минимального элемента      O(logN)
5. Изменение приоритета элемента       O(logN)

Фибоначчиева куча представляет собой набор фибоначчиевых деревьев. 
Фибоначчиево дерево представляют собой k-ричное дерево для которого существует только одно правило: сын не должен превышать своего отца.
Братья-узлы объединены в кольцевой список. Поэтому отцу не обязательно знать всех сыновей. Достаточно иметь ссылочку на одного из них. Минимальный элемент всей кучи – это корень одного из деревьев. Ниже представлен пример фибоначчиевой кучи.

 
Программно будем хранить узел фибоначчиева дерева и саму фибоначчиеву кучу так:

  1. typedef bool (*cmpPtr)(node*, node*);
  2. struct node {
  3. node* parent;     // указатель на отца
  4. node* child;      // указатель на одного из сыновей
  5. node* left;       // указатель на левого брата
  6. node* right;      // указатель на правого брата
  7.  int degree;       // количество дочерних узлов
  8.  bool mark;        // метка - был ли удален один из дочерних элементов
  9.  int key;          // числовое значение узла
  10. };
  11. struct fib_heap {
  12. node* min;        // узел с минимальным корнем
  13.  int roots_amount; // количество узлов
  14. cmpPtr less;      // указатель на функцию-компаратор
  15. }
* This source code was highlighted with Source Code Highlighter.


Рассмотрим работу алгоритма на конкретном примере. Последовательно будет добавлять элементы из массива:

{5,1,3,2,4,0,7,6}

1. Добавление элемента

В начальный момент куча пуста и нет ни одного дерева. Новый элемент “5” становится корнем единственного дерева и одновременно минимальным элементом всей кучи.

Элемент “1” образует новое дерево и отбирает титул минимального элемента кучи у “5”. Каждый новый добавленный элемент будет образовывать новую дерево, а его корень будет добавляться в кольцевой список корней.

Элемент “3” добавляется справа от минимального элемента.

Элемент “2” не меняет минимальный элемент кучи и как и элемент “3” встает справа от минимального корня.

Элемент “1” повторяет судьбу “2”

Элемент “0” становится новым минимальным элементом кучи и также добавляется справа от предыдущего минимального элемента

 
 

Программно функция добавления нового элемента может выглядеть так:

  1. void add(node* Node, node** bro, node* par = NULL) {
  2.     if (*bro == NULL) {
  3.       *bro = Node;
  4.       Node->left = Node;
  5.       Node->right = Node;
  6.     }
  7.     else {
  8.       Node->right = (*bro)->right;
  9.       Node->right->left = Node;
  10.       Node->left = *bro;
  11.       (*bro)->right = Node;
  12.     }
  13.     if (less(Node, *bro))
  14.       *bro = Node;
  15.     if(*bro == min) {
  16.       roots_amount++;
  17.       Node->parent = NULL;
  18.     }
  19.     if (par){
  20.       par->degree++;
  21.       Node->parent = par;
  22.     }
  23. }
  24. node* add(int key) {
  25.     node* Node = new node(key);
  26.     add(Node,&min);
  27.     return Node;
  28. }
* This source code was highlighted with Source Code Highlighter.

2. Определение минимального элемента
Указатель на минимальный элемент кучи хранится в специальном поле. Доступ к нему осуществляется за O(1)

3. Объединение двух фибоначчиевых куч
То, что эта функция работает за константное время выгодно отличает фибоначчиеву кучу от биномиальной и двоичной, где время работы пропорционально O(logN) и O(NlogN).
Т.к. корневые узлы объединены в циклический список, то для объединения двух куч необходимо объединить два циклических списка корней в один. Это можно сделать за константное время путем аккуратного перекидывания ссылок:

  1. struct fib_heap {
  2.   void union_fib_heap(fib_heap &fb) {
  3.     union_root(fb.min,fb.roots_amount);
  4.     if (!min || (fb.min && less(fb.min, min)))
  5.       min = fb.min;
  6.     fb.clear();
  7.   }
  8.   void union_root(node* Node, int nodes_amount) {
  9.     if (Node == NULL) return;
  10.     if (min == NULL) {
  11.       min = Node;
  12.       roots_amount = nodes_amount;
  13.     }
  14.     else {
  15.       node *L = Node->left;
  16.       node *R = min->right;
  17.       min->right = Node;
  18.       Node->left = min;
  19.       L->right = R;
  20.       R->left = L;
  21.       roots_amount += nodes_amount;
  22.     }
  23.   }
  24. };
  25.  
  26. int main() {
  27. fib_heap fh1,fh2;
  28. ...
  29. fh1.union_fib_heap(fh2);
  30. ...
  31. }
* This source code was highlighted with Source Code Highlighter.

4. Удаление минимального элемента
Эта операция является наиболее трудоемкой. Поэтому ее описание разобьем на несколько этапов:
   4.1. Если минимальный элемент имеет детей, то их необходимо сделать корневыми узлами. В этом может помочь функция union_root, рассмотренная ранее. Этот момент будет проиллюстрирован чуть позже.
   4.2. Удаляем минимальный элемент из кольцевого списка корней. Для этого нужно грамотно перебросить ссылочки с левого и правого брата. При этом новым минимальным элементом кучи на время становится правый брат удаляемого элемента. Не факт, что правый брат является минимальным узлом, но после окончания функции будет найден корректный минимальный узел. Может возникнуть такая ситуация, что удаляемый элемент является последним элементов в кольцевом списке. Этот случай наступит, когда min->right == min и его нужно обработать отдельно. В случае, когда удаляемый элемент не является последним, то нужно выполнить процесс уплотнения кучи(consolidate):

  1. int extract_min() {
  2.     node* res = min;
  3.     if (res) {
  4.       childs_in_root(res);
  5.       remove_root(res);
  6.       if (res->right == res)
  7.         min = 0;
  8.       else {
  9.         min = min->right;
  10.         consolidate();
  11.       }
  12.     }
  13.     int ans = res ? res->key : ERROR;
  14.     delete res;
  15.     return ans;
  16. }
* This source code was highlighted with Source Code Highlighter.

   4.3. Процесс уплотнения кучи(consolidate) лучше понять на иллюстрации кучи, которую мы получили на этапе процесса добавления новых элементов. На каждом шаге будут формироваться новые фибоначчиевы деревья размером равным степени двойки. Если на каком-то этапе получается два дерева одинакового размера они объединяются в одно и так повторяется до тех пор пока в наборе остаются деревья одинакового размера.

В итоге получаются 3 дерева уникального размера. Все корни циклического списка, который был вначале обработаны. На этом шаге процесс уплотнения кучи закончен. Отметим, что на текущем шаге уже известен минимальный корень кучи. Он определяется каждый раз, когда образуется дерево уникального размера.

После удаления минимального элемента “1” текущим элементом становится правый его брат “6”, образую первое фибоначчиево дерево размером 1.

Переходим к правому брату элемента “6”, т.к. к “7”, который образует дерево размером 1. Но на предыдущем шаге уже было получено дерево с таким размером. Объединяем их

При слиянии двух деревьев “6” и “7” минимальный корень двух деревьев становится общим корнем. А корень второго дерева становится сыном общего корня. После чего образуется новое дерево размером 2 – “6-7”. Увеличиваем счетчик детей у элемента “2”.

Следующим элементом становится “4”, образуя дерево размером 1. На текущем шаге имеется одно дерево размером 2 и одно дерево размером 1. Поэтому сливать деревья не надо

Новое дерево “2” имеет тот же размер, что и дерево “4”. Сливаем их.

После слияния получается дерево “2-4” размером 2. Но у нас уже есть дерево размером 2 – “6-7”. Поэтому сливаем сливаем эти деревья

При слиянии деревьев на предыдущем шаге образуется дерево размером 4, корнем которого является элемент “2”. Элемент “6” становится сыном элемента “2”. На рисунке нет явной связи “2” и “6”, потому что “6” включена в циклический список с “4”, который является сыном “2”.

Новый дерево “3” имеет уникальную размерность
Далее рассуждения можно продолжить по аналогии с предыдущими шагами.
 
 

Давайте теперь более детально разберем, что происходит в п. 4.1 и 4.2. Допустим, что на текущий момент уже удален минимальный элемент “1” и мы имеем:

Минимальным элементом кучи является 2.
В п.4.1. сказано, что нужно детей минимального элемента поместить в корневой список кучи, что мы и делаем. Далее элемент “2” удаляется и происходит сжатие кучи по вышеописанной схеме.

5. Изменение приоритета элемента
Осталась последняя операция, которую мы разберем. Очевидно, если новый приоритет элемента не ниже, чем приоритет его отца, то ничего делать не нужно. В противном случае действует по следующей схеме:
   5.1. Удаляем текущий элемент A из кольцевого списка братьев и если отец A(P) ссылался на этот элемент A, то перебрасываем ссылку child элемента P на правого брата A. Уменьшаем счетчик количества сыновей у P и делаем метку mark равную true. Это означет, что у элемента P был удален сын. Данная метка указывает на то, что если возникнет такая ситуация, что у одного узла будет удалено более одного сына, то его нужно поместить в кольцевой список корней.
   5.2 Добавляем элемент A в кольцевой список корней. Если приоритет элемента A меньше минимального корня, то элемент A становится минимальным элементом кучи.
   5.3. Делаем каскадное вырезание. То, о чем идет речь в п.5.1. Если у отца элемента A – элемента P ранее удалялся сын, то необходимо выполнить поместить элемент P в кольцевой список корней. Далее продолжить п.5.3. для отца элемента P, если у него также ранее удалялись сыновья.


Задача:
EZDIJKST
Решение: здесь
Примечание: полная реализация фибоначчиевой кучи

понедельник, 31 октября 2011 г.

Занятие №9 (Методы тестирования задач)

                                                    [Все занятия]

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

Учебные задачи:
   Задача A.
   [Тестирование целых точек отрезка]
В тесте нет ничего сверхъестественного. Особое внимание нужно уделить случаю, когда точки лежат на прямой, параллельной одной из осей.

   Задача B. 
   [Тестирование сортировки] [Генератор тестов]
С этой задачей я промучился очень долго. Я даже готовил слезный пост, с мольбами о помощи, в котором описал свои рассуждения по поводу этой задачи. Но так получилось, что когда был готов генератор тестов, первый же им сгенерированный набор зашел на OK. Приведу основной фрагмент того слезного поста:
Какие тесты будем делать?
1) Генерируем рандомные числа во всем диапазоне. Размер массива немаксимален.
2) Все тоже самое, но размер массива максимален.
3) Упорядоченный массив. Лучше захватить и отрицательные и положительные числа
4) Обратный массив по аналогии с 3 тестом.
5) Массив из одного элемента(пускай отрицательного). Проверка на потенциальные Run-time errors.
6) Массив из двух элементов (отрицательного и положительного)
7) Массив не максимальной длины, который представляет собой кучу.
8) Массив с одинаковыми элементами. В том числе и по модулю. Так чтобы положительные числа были перед отрицательными.
9) Массив с одинаковыми элементами. Неотрицательными
10) Массив с одинаковыми элементами. Неположительными”.
Олимпиадные задачи:
   Задача A.
  
[Распаковка строчки]
Задача для начинающих на аккуратную реализацию. 
   Задача B.
  
[Сортировка масс]
Нужно быть внимательным в выборе типов данных. 
   Задача C.
  
[Результаты олимпиады]
Несложная задача, но условие наводит ужас обилием различных вариантов проверок. На практике все оказалось не так страшно: само решение занимает меньше места чем ввод данных =) 
Дополнительные олимпиадные задачи:
   Задача A.
  
[Проверьте правильность ситуации]
С первого взгляда задача кажется несложной. Но нужно быть внимательным и аккуратным. 
   Задача B.
  
[Гражданская оборона]
Задача на умение писать компараторы. Удобно использовать граничные элементы, чтобы избежать лишние проверки. 
   Задача C.
  
[Переключение между окнами]
Задача на умение пользоваться списком и выполнять операции удаления элемента и вставки его в конец. Пришлось повозиться со случаем, когда имя программы представляет пробельные символы.

Алгоритм Кнута-Морриса-Пратта

                         По мотивам лекции Сагунова Данила и реализации indy256

Алгоритм относится к разряду алгоритмов поиска подстроки в строке.

Префиксом строки S называется подстрока строки S, первый символ которой совпадает с первым символом строки S.
Суффиксом строки S называется подстрока строки S, последний символ которой совпадает с последним символом строки S.
Длина префикса и суффикса строки S строго меньше длины строки S.
Префикс функция от строки S: П(S) – это максимальная длина префикса S, совпадающего с её суффиксом.
Z-функция от строки S – это массив длинной равной длине строки S, где Z[i] – это префикс функция от подстроки S, последний символ, которой равен S[i].

Пусть S = “abababaaabababac”
z[0]  = П(“a”)                = 0
z[1]  = П(“ab”)               = 0 
z[2]  = П(“aba”)              = 1
z[3]  = П(“abab”)             = 2
z[4]  = П(“ababa”)            = 3
z[5]  = П(“ababab”)           = 4
z[6]  = П(“abababa”)          = 5
z[7]  = П(“abababaa”)         = 1
z[8]  = П(“abababaaa”)        = 1
z[9]  = П(“abababaaab”)       = 2
z[10] = П(“abababaaaba”)      = 3
z[11] = П(“abababaaabab”)     = 4
z[12] = П(“abababaaababa”)    = 5
z[13] = П(“abababaaababab”)   = 6
z[14] = П(“abababaaabababa”)  = 7
z[15] = П(“abababaaabababac”) = 0

Можно заметить, что z-функция может увеличиваться за один шаг не более чем на 1, а уменьшиться на произвольное количество.


  1. void prefix_func(const string &str, vector<int> &z) {
  2.  
  3.   z.resize(str.size());
  4.   z[0] = 0;
  5.   for (int i=1;i<z.size();++i) {
  6.     int pos = z[i-1];
  7.     while (pos > 0 && str[pos] != str[i])
  8.       pos = z[pos-1];
  9.     z[i] = pos + (str[pos] == str[i] ? 1 : 0);
  10.   }
  11. }
* This source code was highlighted with Source Code Highlighter.

Ключевым моментов в функции подсчета Z-функции является цикл while(7-8 строки). На каждом шаге пытаемся увеличить длину префикса, равного суффиксу. Если это сделать не удается, то необходимо уменьшить размер префикса максимальным образом.

Рассмотрим нахождение z[7]. Текущая подстрока “abababaa”, z[6] = 5.
На шаге 7 пытаемся продолжить увеличивать длину префикса.
1) Сравниваем 5-ый символ с последним: ”abababaa
2) Необходимо максимальным образом уменьшить длину префикса. Для этого нужно найти префикс префикса, который обязательно будет равен суффиксу суффикса. П(”ababa) = 3
3) Сравниваем 3-ый символ с последним: “abababaa”. Продолжаем рассуждения пока префикс существует, т.е. пока имеет ненулевую длину, либо до совпадения концов префикса и суффикса. П(“aba”) = 1.
4) Сравниваем 1-ый символ с последним: “abababaa”. П(“a”) = 0.
5) Сравниваем 0-ой символ с последним: “abababaa”. Успех =)
Значит z[7] = 1.

Вернемся к исходной задаче поиска подстроки(S) в строке(TEXT). Если не хочется заморачиваться, а главное если есть такая возможность, то в общем случае можно получить строку TEXT’ = S + sep + TEXT, где sep – это символ, который гарантированно не встречается в строках S и TEXT, а “+” – это конкатенация строк. Затем найти z-функцию от TEXT’. Если z[i] = длина(S), значит S является подстрокой строки TEXT.

  1. void kmp() {
  2.   text = str + "#" + text;
  3.   z.resize(text.size(), -1);
  4.  
  5.   z[0] = 0;
  6.   for (int i=1;i<text.size();++i) {
  7.     int pos = z[i-1];
  8.     while (pos != -1 && text[i] != text[pos])
  9.       pos = pos - 1 >= 0 ? z[pos-1] : -1;
  10.     z[i] = pos + 1;     
  11.   }
  12. }
  13. void output() {
  14.   for (int i=0;i<text.size();++i) {
  15.     if (z[i] == str.size()) {
  16.       cout<< i - 2*str.size() <<' ';
  17.     }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.

Понятно, что в данной реализации происходит лишнее выделение памяти, и не всегда есть возможность вести себя так вальяжно.

Более эффективная реализация:

  1. void prefix_func(const string &str, vector<int> &z) {
  2.  
  3.   z.resize(str.size());
  4.   z[0] = 0;
  5.   for (int i=1;i<z.size();++i) {
  6.     int pos = z[i-1];
  7.     while (pos > 0 && str[pos] != str[i])
  8.       pos = z[pos-1];
  9.     z[i] = pos + (str[pos] == str[i] ? 1 : 0);
  10.   }
  11. }
  12. void kmp(const string &text, const string &str) {
  13.   vector<int> z;
  14.   prefix_func(str,z);
  15.   int pos = 0;
  16.   for (int i=0; i<text.size(); ++i) {
  17.     while (pos > 0 && (pos >= str.size() || str[pos] != text[i]) )
  18.       pos = z[pos-1];
  19.     if (text[i] == str[pos]) pos++;
  20.     if (pos == str.size())
  21.       printf("%d ", i - pos + 1);
  22.   }
  23. }
* This source code was highlighted with Source Code Highlighter.

Здесь сначала считается z-функция для строки S, а потом происходит эмуляция первой реализации, как будто строка S является префиксом строки TEXT. Как видно в данном случае затраты на память сократятся.

Попрактиковаться можно здесь:
spoj.pl - NHAY 
acmp.ru – Поиск подстроки

воскресенье, 23 октября 2011 г.

Занятие №8. Динамическое программирование с двумя и более параметрами

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

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

Учебные задачи:
  
Задача A.
  
[Наибольшая общая подпоследовательность (НОП)]
В данной задаче можно применить классический алгоритм Нудельмана-Вунша.
   Задача B.
  
[Наибольшая общая подпоследовательность с восстановлением ответа]
Продолжение предыдущей задачи с той разницей, что в текущей реализации использовались барьерные первый столбец и строка.
   Задача C.
  
[Биномиальные коэффициенты]
Наверное последняя проходная задача на ДП в этом цикле. Суть задачи сводиться к классической черепашке. 
Олимпиадные задачи:
 
Задача A.
  
[Движение по полосам] 
Очень хорошая задача. Решаем ДП с двумя параметрами: количество использованных полос(s), количество использованных дорог(r). Ответом на вопрос будет являться значение dp(n,m), где n – общее количество полос, m – общее количество дорог. Чтобы найти значение на текущем шаге dp(s,r), необходимо перебрать и сложить все возможные значения dp(s-1,r’).
   Задача B.
  
[Еловая аллея] 
Данная реализация отражает идею, предложенную в разборе, но имеет сложность M*M*N.
   Задача C.
  
[Почти палиндром]
Классическая LR динамика. Нужно быть осторожным в выборе типа данных для элементов таблицы. 
Дополнительные олимпиадные задачи:
 
Задача A.
  
[Электронная почта]
Суть задачи сводится к поиску оптимальной стратегии в игре Zuma, с одним только отличием, что нет минимального количества рядом стоящих шариков, которые могут быть удалены за один раз. В обычной игре это число равно 3. На spoj.pl есть задача ZUMA, в которой как раз фигурирует это минимальное значение рядом стоящих шариков.
Решать будем двумерной LR динамикой. В таблице dp[i][j] находится оптимальный ответ для подмассива с i-ого по j-ый элементы. Базой динамики будут служить два факта:
1) if (i > j)  dp[i][j] = 0
2) if (i == j) dp[i][j] = 1
Теперь рассмотрим общий случай для произвольных i и j:
I) Очевидно, что может быть такая ситуация, когда исходный массив можно разбить на набор  непересекающихся подмассивов и последовательно избавиться от каждого из них. Например для массива A =  {1, 2, 2, 3, 4, 5, 5, 5} это будет оптимальная стратегия. Этот случай обрабатывается в строках 40-41.
II) Отдельно стоит рассмотреть случай, когда элементы a[i] и a[j] равны. Возможно стоит сначала избавиться от подмассива [i+1, j-1], а потом за одну итерацию убрать крайние элементы за одну итерацию. Например для массива B = {1,,2,3,4,5,5,5,4,3,2,1} это будет оптимальная стратегия. Этот случай обрабатывается в строке 44.
III) Продолжим рассматривать случай, когда граничные элементы подмассива равны. Может возникнуть такая ситуация, когда есть элемент a[i] == a[k] == a[j], причем i < k < j. При этом выгодно сначала избавиться от подмассива [i+1,k-1], чтобы элементы a[i] и a[k] встали рядышком, либо же избавиться от подмассива [k+1,j-1], чтобы рядом оказались элементы a[k] и a[j]. Например для массива С = {1,2,3,4,3,2,1,5,6,7,6,5,1} оптимальной стратегия будет III с элементами II(для удаления подмассивов межды единицами). Этот момент обрабатывается в строках 45-49. 
   Задача B.
  
[Плитки]
Шикарная задача на динамику по рванному краю(динамика по профилю). 
Будем заполнять таблицу dp[clr][len][mask], где clr – цвет, на который заканчивается последовательность длины len, удовлетворяющая битовой маске mask. Разберемся с битовой маской.
Сразу оговоримся, что предложенное решение использует маску, ориентированную на несимметричную матрицу цветов. Условно обозначим 3 возможных цвета как R,G и B. Тогда имеем матрицу:
   R G B
R  0 1 2
G  3 4 5
B  6 7 8
На пересечении цветов указано значение row * 3 + col, где row – номер строки, col – номер столбца. Получаем следующий массив:
8  7  6  5  4  3  2  1  0   - номер сочетания цветов
BB BG BR GB GG GR RB RG RR  - сочетание цветов
Пусть номер сочетания цветов указывает на бит в маске. 
Зафиксируем для таблицы dp значение clr, len и mask. Номер единичного бита в mask говорит о том, что сочетание цветов, соответствующего номеру бита уже было в конце строки в диапазоне [len,n-1].
Отсюда можно получить базу динамики. Перебрав все пары цветов c1 и с2, в случае валидной комбинации c1-c2 dp[c1][n-2][code(c1,c2)] = 1. Случай, когда длина строки равна 1 можно рассмотреть отдельно.
Подсчет всех остальных значений отображен в строках 104-120:
Для фиксированных c1, c2, len, mask можно однозначно определить ответ:
dp[c1][len][mask] = dp[c2][len+1][mask] + dp[c2][len+1][mask ^ cur_mask], где cur_mask – закодированная комбинация цветов c1 и с2. Говоря другими словами последовательность, заканчивающаяся цветом c1 длины len и маской mask могла получиться из строки, заканчивающейся цветом c2, длины len+1 с той же маской, а также маской, в которой ранее не использовалось сочетание цветов c1 и с2.

Ответ формируется из элементов dp[c][0][mask], где с принимает все возможные значения цветов, а mask принимает все возможные валидные комбинации цветов, содержащие всю матрицу цветов.
   Задача C.
  
[Симпатичные узоры возвращаются]
Задача является логическим продолжением задачи Симпатичные узоры, которое наверное является классикой динамики по рваному контуру. Ее разбор дан в лекции. Здесь лежит мое решение.
Исходная задача также разобрана в лекции. Суть ее сводится к быстрому перемножению матриц. Данный подход использовался в алгоритме для нахождения достижимости за k шагов произвольной вершины j из произвольной вершины i. Там нужно было возвести исходную матрицу смежности в степень k.

четверг, 20 октября 2011 г.

Система непересекающихся множеств (Disjoint set union)

Если мы работаем с объектами, которые во время работы могут объединяться в группы. Причем эти группы попарно не имеют общих элемент(непересекающиеся множества). То скорее всего нам пригодится структура данных “Система непересекающихся множеств” (DSU). С помощью нее можно сделать две операции:
1) int find_set(X) - определение множества, в котором находится элемент X. При этом множество определяется одним(лидирующим) элементом.
2) void union_set(X,Y) - объединение множества, в котором находится элемент X с множеством, в котором находится элемент Y.

Полный обзор этой темы можно найти на емаксе.

Множества будут представлены в виде леса(набор деревьев), т.е. каждое множество будет являться деревом. При этом для каждого элемента будет храниться его предок. Это проще всего сделать с помощью массива parent. В начальный момент времени каждый элемент будет являться предком для самого себя, т.е. каждое дерево состоит из одного элемента.

  1. void init() {
  2.   for (int i=1;i<=n;i++)
  3.     parent[i] = i;
  4. }
* This source code was highlighted with Source Code Highlighter.

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

  1. int find_set(int x) {
  2.   if (parent[x] == x)
  3.     return x;
  4.   return parent[x] = find_set(parent[x]);
  5. }
* This source code was highlighted with Source Code Highlighter.

Теперь давайте рассмотрим операцию объединения двух множеств. При объединении двух множеств выбирается один лидирующий элемент. Очевидно, что он должен быть лидирующим элементов одного из объединяемых множеств. Какое же множество выбрать? Нужно меньшее множество присоединять к большему. Это целесообразно, потому что придется переопределять нового предка для меньшего количества элементов.

  1. void union_set(int x, int y) {
  2.   x = find_set(x);
  3.   y = find_set(y);
  4.   if(x != y) {
  5.     if (size[x] < size[y])
  6.       swap(x,y);
  7.     parent[y] = x;
  8.     size[x] += size[y];
  9.   }
  10. }
* This source code was highlighted with Source Code Highlighter.

Как видно был заведен еще один массив size, в котором на [i] месте хранится количество элементов в дереве, корнем которого является элемент [i]. Но можно обойтись без дополнительного массива подружившись с рандомом.

  1. void union_set(int x, int y) {
  2.   x = find_set(x);
  3.   y = find_set(y);
  4.   if (rand()&1)
  5.     parent[x] = y;
  6.   else
  7.     parent[y] = x;
  8. }
* This source code was highlighted with Source Code Highlighter.

Как показывает практика существенных замедлений такое решение не дает.
Существенным минусом DSU является то, что нельзя одно множество разбить на два. Но даже несмотря на это у DSU целый паровоз применений (см. емакс)

Для закрепления материала предлагаю решить две несложные задачи:
1) [Острова] (DSU в чистом виде) [Решение]
2) [Паутина Ананси] [Решение]

пятница, 14 октября 2011 г.

Занятие №7. Динамическое программирование с одним параметром

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

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

Учебные задачи:
  
Задача A.
  
[Взрывоопасность]
Очевидно, если N = 1, то возможны два варианта: “А” и “B”. Если N = 2, то можно получить сразу две последовательность, заканчивающиеся на ‘B’, приписав ее к каждой последовательности, получившейся на предыдущем шаге, т.е. последовательности “AB” и “BB”. ‘A’ можно приписать только к одной последовательности “B”, получив “BA”. Итого, для N = 2 получили 3 варианта. Обозначим dp[i] – количество вариантов, которые можно получить из i-блоков. Продолжая рассуждения в той же духе можно заметить, что для любого i можно получить dp[i-1] последовательностей, приписав к ним блок ‘B’, а также dp[i-2] последовательностей, которые заканчиваются на ‘B’, к которым можно приписать блок ‘A’. В итоге получаем рекуррентную формулу dp[i] = dp[i-1] + dp[i-2]. Что является формулой вычисления числе Фибоначчи.
В классическом виде данная задача формулируется так: сколькими способами можно записать последовательность длины N из 0 и 1 без двух подряд идущих нулей. 
   Задача B.
  
[Наибольшая возрастающая подпоследовательность (НВП)]
Данную задачу мы уже решали несколько раз [1C из курса Меньшикова]. Но всегда полезно повторить изученное. В данном решении я привел квадратичное решение. С более быстрым решением можно ознакомится в разборе задачи 1C.
   Задача C.
  
[0-1 Рюкзак]
Классическая задача на ДП, которую нужно уметь решать. На каждом шаге пытаемся набрать вес(j+w[i]), который формируется из веса гарантировано набранного на предыдущих шагах(j) + веса текущей вещи(w[i]). Стоимость такой новой комбинации формируется из стоимости вещей, набранных на предыдущем шаге(dp[j]) + стоимость текущей вещи(p[i]). Если получается так, что новая стоимость для веса j+w[i] более предпочтительна, т.е. превышает стоимость, полученную для этого веса на предыдущих шагах, то нужно обновить ее с учетом i-ой вещи. Суть сказанного иллюстрирует эта строка:

dp[j+ w[i]] = max(dp[j+ w[i]], dp[j] + p[i]);

Отметим тот факт, что изначально весь массив dp заполнен –1, а dp[0] = 0.
Олимпиадные задачи:
  
Задача A.
  
[Покупка билетов]
На каждом этапе пытаемся получить оптимальный ответ для первых N человек. Возможно лучшим решением было бы завести первые три барьерных элемента, но я ручками подсчитал первые три решения для n = 0,1 и 2, а дальше запустил цикл с рекуррентной формулой. 
   Задача B.
  
[Две стены]
Сразу сделаем важную оговорку. Необходимо использовать все кирпичи в наборе. Поэтому если вдруг получилось так, что сумма длин всех кирпичей цвета A не равна сумме длин кирпичей цвета B, значит построить две прямоугольные стены уже не получится. Будем использовать подход, который использовали в решении задачи о рюкзаке. А именно будем искать все возможные комбинации длин, которые можно получить из кирпичей одного цвета. Пусть SUM – сумма длин всех кирпичей одного цвета. Тогда необходимо найти такое значение SEP, что для каждого цвета можно набрать длину SEP и SUM-SEP. Если это сделать удалось, значит решение найдено.
   Задача C.
  
[Репортаж]
Задача легко решается, что мы умеем решать задачу B из предыдущего блока, где нужно находить наибольшую возрастающую подпоследовательность(LIS). Для начала найдем LIS для исходного массива, а потом проделаем тоже самое только LIS будем искать не слева направо, а справа налево. В итоге останется только найти такую позицию в исходном массиве, для которой минимальное значение меньших элементов справа и слева будет максимально.
Дополнительные олимпиадные задачи:
 
Задача A.
  
[Отчет]
Задача сводится к поиску максимальной подпоследовательности, в которой возрастает общий объем производства и убывает процент бракованных изделий. Суть решения мало чем отличается от поиска LIS.
   Задача B.
  
[Словарь]
Для каждой позиции i в тексте будем искать слово, на которое оно может оканчиваться. Для этого можно перебрать все слова(ограничения позволяют) из словаря и проверить можно ли сформировать текст, заканчивающийся позицией i – size, где size – длина текущего слова.
   Задача C.
  
[Валютные махинации]
Несложная задача. Ее можно было дать и в учебных задачах, потому как она позволяет прочувствовать суть ДП на простом примере. Для каждого дня будем искать максимальное количество рублей, долларов и евро, которое можно получить за первые дни, оканчивающихся текущим. Максимальное количество рублей для текущего дня будет равно максимальному из значений:
1) Максимальное количество рублей с предыдущего дня
2) Максимальное количество долларов с предыдущего дня, переведенное по сегодняшнему курсу в рубли. 
3) Максимальное количество евро с предыдущего дня, переведенное по сегодняшнему курсу в рубли.
Доллары и евро ищутся по схожей схеме.

вторник, 4 октября 2011 г.

Занятие №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. А транспонирование подматрицы будет идентично реверсу побочной диагонали, или обмену двух соседних элементов текущей диагонали. При упорядочивании диагонали будем использовать принцип аналогичный сортировки пузырьком.