задача Футурама (3298 на informatics.mccme.ru)

Условие
Эта задача показалась мне довольно интересной. Тем более, что она имеет схожие черты с другой очень хорошей задачей D++.

Итак, суть сводится к тому, что нужно упорядочить массив с учетом того, что последние два элемента гарантированно находятся на своих позициях. Элементы, находящиеся на позициях i и j запрещается менять местами, если ранее уже совершались обмены i-ого и j-ого элементов.
Из условия нам дают понять как можно обменять два элемента местами, используя два последних элемента. Пусть нужно обменять элементы 3 и 4, находящихся на позициях i и j:

Теперь нужно вспомнить, что исходный набор чисел является перестановкой. Это позволяет разложить имеющуюся перестановку на циклы и уже в дальнейшем работать с каждым циклом отдельно.
Понятно, что если упорядочить элементы в каждом цикле, то исходная перестановка станет единичной, т.е. упорядоченной.
В представленном решении не нужно помнить о запрещенных позициях для обменов, т.к. они все будут осуществляться через последние два элемента. Для любого цикла перестановки справедлив один из случаев:
1) Длина цикла равна 1. Понятно, элемент цикла находится на “нужном” месте в перестановке и ничего делать не нужно
2) Длина цикла равна 2. В данном случае элементы цикла можно обменять местами по правилу изложенному выше
3) Длина цикла больше 2. Это самый сложный случай. Рассмотрим перестановку A = {5,6,4,1,3,2,7,8}:

Один из циклов перестановки С = 1-5-3-4-1. Поставим на свои элементы цикла, отличные от двух последних(1 и 4), т.е. 5 и 3. Это можно сделать с помощью промежуточных обменов с предпоследним элементом перестановки:

Получилась перестановка B = {7,6,3,1,5,2,4,8}. Теперь немного отвлечемся и рассмотрим перестановку
A’={4,6,3,1,5,2,7,8}. Она имеет цикл С’ = 1-4, в то время, как элементы 3 и 5 находятся на “своих” местах. Для упорядочивания цикла C’ можно воспользоваться п.2)
Перестановка B получается из перестановки A’ после первого же обмена. Поэтому чтобы закончить п.3) необходимо выполнить оставшиеся 3 обмена, чтобы обменять в перестановке A’ элементы 1 и 4:

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

Решение

Contest list

В данном посте буду формировать список прорешенных контестов.

Div1:
1[+]. Московская командная олимпиада 2003
[15Jan12 - 17Jan12]     [Условие]
    A. Перегоны                    (алгоритм Флойда)
   $B. Сломанный калькулятор       (Теория чисел)
    C. Валютные махинации          (ДП-1) (* цифра после ДП означает уровень сложности: 1 – легкая)
    D. Двухтуровая олимпиада       (Моделирование)
    E. Черно-белые палиндромы      (Строки, Хеширование)
    F. Луч света в темном царстве  (Моделирование, Матрицы)
    G. Распаковка строчки          (Строки)
   *H. Дремучий лес                (Геометрия)
2[+]. Московская командная олимпиада 2004
[31Dec11-03Jan2012]     [Условие]
    A. Москва – сортировочная  (Поощрительная)
    B. Кафе                    (ДП-2)
    C. Euro-English            (Строки - муторные)
  $$D. D++                     (Моделирование. Цикл перестановки)
   $E. Скобки                  (ДП-2)
    F. Двоякие числа           (Поощрительная. Теория чисел)
   *G. OOO                     (Геометрия – 25 случаев)
    H. Калах                   (Моделирование)
    I. Сортировка масс         (Сортировка. Тип данных)
3[+]. Московская командная олимпиада 2005
[05Jan12 - 11Jan12]     [Условие]
    A. Результаты олимпиады      (Моделирование)
    B. Сокращение дроби          (GCD)
    C. Современники              (Сортировка. Моделирование)
   $D. Тройки чисел              (Теория чисел)
   $E. T2005(Sort)  T2005(Бор)   (Сортировка. Бинарный поиск / Бор)
    F. Роботы                    (Теория графов. Моделирование. Поиск в ширину. Битовая маска)
   $G. Монетки                   (Перебор. 2^30 > 3^15)
    H. Сверим часы               (Моделирование. Время)
   *I. Разрезанный прямоугольник (Геометрия)
   $J. Количество треугольников  (Арифметическая прогрессия)
4[+]. RROI–2012(Региональный этап всероссийской олимпиады школьников 2011-2012) 
[27Jan12 - 31Jan12]     [Условие]                                          [Разбор от М.Гуровица]
    A. Цапли                 (Поощрительная)
    B. Круглый стол          (Моделирование)
    С. Поврежденный XML      (Строки, Полный перебор) 
  $*D. Игра с числами        (Теория игр)
    E. Кондиционер           (Поощрительная)
    F. Космический кегельбан (Геометрия)
    G. Abracadabra           (Бор, Хеширование)


Div2(исходники и разборы только самых интересных задач):
1[+]. Московская индивидуальная олимпиада 7-9 класс (2006) [28Dec2011]
    С. Кинотеатр [второе решение]  (Мальчики/Девочки)
    E. Метро                       (Поиск в ширину) 
2[+]. Московская индивидуальная олимпиада 7-9 класс (2007) [28Dec2011]
    D. Кассы    (Время)
    E. Словарь  (ДП-2)
3[+]. Московская индивидуальная олимпиада 7-9 класс (2008) [19Jan2012]
    A. Автобусы (Моделирование. Мальчики/Девочки)
    D. Реклама  (Быстрая сортировка)
4[+]. Московская индивидуальная олимпиада 7-9 класс (2009) [26Dec2011]
    D. Изобретательный Петя (Строки. Хеширование) 
5[-]. Московская индивидуальная олимпиада 7-9 класс (2010)
6[+]. Московская индивидуальная олимпиада 6-9 класс (2011) [04Feb2012-10Feb2012]
   *D. Поход      (ДП-2)
   $E. Футурама   (Цикл перестановки) + [пост]

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 не могли ошибаться =).

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

Задача: “Дается строка 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*x¹ + b
h(3) = h(“abc”)     = a*x² + b*x¹ + c
h(4) = h(“abcd”)    = a*x³ + b*x² + c*x¹ + d
h(5) = h(“abcda”)   = a*x⁴ + b*x³ + c*x² + d*x¹ + a
h(5) = h(“abcdab”)  = a*x⁵ + b*x⁴ + c*x³ + d*x² + a*x¹ + b
h(5) = h(“abcdabb”) = a*x⁶ + b*x⁵ + c*x⁴ + d*x³ + a*x² + b*x¹ + 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: Все вычисления ведутся без модульной арифметики. Поэтому интервал возможных значений полиномиальной хеш-функции равен 2⁶⁴.

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.

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

Сортировка большого файла с целыми числами: Генератор тестов (Часть 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 ждем от Сагунова Данила.

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