Занятие №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 – Поиск подстроки

Занятие №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.

Система непересекающихся множеств (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) [Паутина Ананси] [Решение]

Занятие №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) Максимальное количество евро с предыдущего дня, переведенное по сегодняшнему курсу в рубли.
Доллары и евро ищутся по схожей схеме.

Занятие №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.