Олимпиада IT-CON 2014. Разбор + Материалы + Монитор

Условия задач

A. Единицы
В этой задаче нужно было уметь находить количество единиц в строке и в числе
Решение

B. Коллекционер
Необходимо было найти количество уникальных элементов во входном массиве.
Задачу можно было решать как минимум двумя способами.
1. Воспользоваться контейнером, хранящим уникальные ключи. Например множеством
2. Отсортировать входной массив и найти количество пар, состоящих из соседних элементов, значения которых не равны.
Решение

C. Декодирование по Хаффману
Задача решается жадно. Для хранения соответствия между буквенным и двоичным представлением можно было воспользоваться map’ом или хеш-таблицей, где в качестве ключа выступала бы двоичная интерпретация буквы алфавита.
Перебираем все символы исходного сообщения слева направо. Если в какой-то момент времени на текущим префиксе удалось набрать одно из двоичных представлений алфавита, то выводим эту букву в ответ. Отсекает текущий префикс и повторяем поиск очередной буквы.
Данный подход возможет благодарю свойству кода Хаффмана: никакой код буквы алфавита не является префиксом для другого кода этого же алфавита.
Решение

D. Восстановление перестановки
От участников требовалось реализовать квадратичное решение.
Авторское решение разматывала клубок, начиная с максимального элемента перестановки.
Можно заметить, что максимальный элемент перестановки будет соответствовать самому правому нулю в таблице инверсий. После нахождения такого элемента его можно “вырезать” и уменьшить все элементы из таблицы инверсий, находящихся правее этого элемента. Далее нужно повторить поиск максимального элемента в модифицированной перестановки(без учета вырезанного элемента) и так до тех пор, пока не найдутся все элементы перестановки
Решение

E. Калькулятор
Очень красивая и несложная задача на динамическое программирование.
Заведем массив на n элементов(N <= 1000000)
Для каждого i <= n найдем ответ на данную задачу.
Начнем с базы динамики. Для i = 1, очевидно, что ответ будет 0. Далее переберем все элементы в интервале [2,n]. В текущий элементы i мы могли попасть из трех состояний: i-1, i/2, i/3. Необходимо выбрать предыдущее состоянии, которое может быть набрано за минимальное количество действий. Также необходимо учесть, что состояния i/2 и i/3 можно рассматривать только в том случае, если i делится на 2 и на 3 без остатка.
Решение

F. Генерация Z-матрицы
Решение задание подразумевало рекурсивную реализацию заполнения матрицы. Реализацию рекурсивных переходов и расчет границ блоков смотрите в авторском решении. В данном решении матрица 2*2 заполняется в двойном цикле, но можно было оставить рекурсивный переход до матрицы 1*1.
Решение

G. Буквы по кругу
Задачу нужно было свести к поиску подстроки в строке
Решение

H. Объезд королевства
Классическая задача на перебор с возвратом. Ограничения были подобраны так, чтобы задача укладывалась в time limit.
Решение

I. Следующий палиндром
Задача на аккуратность реализации и на учет всех случаев. Особое внимание стоит уделить центральному элементу палиндрома в случае нечетной длины, а также увеличению размера палиндрома(например при входном палиндроме 99 ответ будет 101)
Решение

J. Карточная пирамида
Задачу можно было решать с помощью формулы, зная формулу арифметической прогрессии
Решение

Условия задач: http://goo.gl/nqvfJk
Полный монитор: http://goo.gl/wkbAOu
Тесты: http://goo.gl/QwmEee

Победители:

Победители IT-CON 2014

Лучший участник олимпиады от компании Mirafox (Евгений) – 2 место в общем зачете

Олимпиада IT-CON 2013. Разбор + Материалы + Монитор

Условия задач

A. Счастливые билеты
Суть задачи сводится к грамотному написанию двух функций:
   1. Проверка счастливости по-московски
   2. Проверка счастливости по-питерски.
Задача имела поощрительный характер.
Решение
  
B. Пагинация
Задача решается очень просто, если нумерации участников и листов вести с нуля. А именно:
n / k – номер листа
n % k – номер строки на нужном листе.
Для перехода на нумерацию с единицы можно было воспользоваться таким приемом:
(n - 1) / k + 1 – номер листа
(n - 1) % k + 1 – номер строки.
Решение

C. Палиндромы
Еще одна поощрительная задача. Суть ее сводится к написанию функции проверки строки на палиндромность:

bool is_palindrome(const string &s){
	int l = 0, r = s.size() - 1;
	while (l < r) {
		if (s[l++] != s[r--])
			return false;
	}
	return true;
}

Решение

D. Арифметическая прогрессия
Пожалуй самая сложна задача =).
Решение

E. Права пользователя
В задаче предполагалось использовать битовые операции и умение использовать структуру данных “словарь”. Ключевой момент – умение установить i-ый бит число в 1 или в 0. Более подробно о распространненных битовых операциях можно почитать здесь.
Решение
 
F. Шифр Кардано
Смысл задачи сводится к умению поворачивать квадратную матрицу по часовой стрелке.

void transposition(int mask[][SIZE]){
	int tmp[SIZE][SIZE];
	for (int i=0;i<n;++i){
		for (int j=0;j<n;++j){
			tmp[i][j] = mask[n-j-1][i];
 
		}
	}
	memcpy(mask,tmp,sizeof(tmp));
}

Решение

G. Количество секретных баз
Данную задачу можно было решать по-разному. Рассмотрим два решения.
1. Рекурсивная закраска связных областей
   По сути дела в условии задачи нет информации о том, что кроме военных баз на карте могут находиться другие объекты. Также сказано, что военные базы не пересекаются и не соприкасаются. Поэтому можно смело свести задачу к поиску количества компонент связностей, реализуя обычный DFS(поиск в глубина)
2. Поиск самой северной точки военной базы.
   Рассмотрим военную базу размером 2:

Для того,чтобы проверить является ли текущая точка самой северной точкой базы нужно посмотреть на три соседние клетки: вверх, вправо и влево. Если все три клетки не заняты военной базой, значит текущая точка является самой северной.
Решение DFS
Решение (Поиска самой северной точки) 

H. T9
Еще одна несложная задача. На первом этапе переводим строковое представление контакта в цифровой ряд, который нужно набрать. При этом нужно обратить внимание на:
1) Возможное наличие пробелов в начале и в конце строкового представления контакта. На этом моменте падали почти все решения. 
2) Нужно хранить изначальный вариант контакта для его последующего вывода
3) Корректно обрабатывать буквы в разных регистрах.
Решение

I. Пятнашки 3x3
В самом худшем случае любые пятнашки размером 3x3 можно собрать не более за 31 шаг. Данную задачу по замыслу жюри нужно было решать BFS’ом, но в последний момент было принято решение ослабить максимальное количество шагов до 15. В результате получилось, что грамотно написанный DFS без меморизации заходил в установленные лимиты.
В написании BFS’а есть интересный момент:
Как организовать быструю проверку – было ли данное состояние пройдено на предыдущих шагах. Тут можно воспользоваться двумя подходами:
  1) Ленивый. Представим поле в виде 9-ти значного числа, которое состоит из цифр поля, записанных слева направо, сверх вниз. Пустое поле будем кодировать нулем. При этом получается, что самое большое число, которое может быть 876543210, которое с успехом помещается в int. Общее количество всех валидных состояний в пятнашках равно 9! / 2 = 181440. Поэтому для хранения все предыдущих состояний можно использовать множество, в котором хранить закодированное состояние пятнашки. Используя множество можно с логарифмической сложностью ответить на вопрос – было ли данное состояние пройдено на предыщущих шагах
   2) Комбинаторный. Используем всю ту же логику что в первом пункте, но обращаем внимание на то, что общее количество всех перестановок сравнительно невелико. Если каждое закодированное состояние пятнашки представимо в виде перестановки, то состояние пятнашки можно кодировать не самой перестановкой, а ее порядковым номером в лексикографическом порядке. Получается что что можно множество заменить на битовый массив размером 9!. Сложность поиска текущего состояние среди предыдущих уменьшается до O(1).

BFS можно заменить на алгоритм A*. В качестве оценочной функции можно использовать сумму манхэттенских расстояний для каждой цифры. Начальная позиция цифры совпадает с ее позицией в текущем состоянии. Конечная позиция – позиция цифры в финальном состоянии. Чем меньше оценочная функция тем ближе данное состояние к финишу.
Решение

Арифметическое выражение
Последняя задачу на динамику. Будем последовательно будем находить ответ на задачу для каждого числа от 0 до n.
Пусть len(j) – длина арифметического выражения для числа j. Если число j нельзя набрать, то длина равна 0.

Текущее число i можно набрать тремя способами:
1) Непосредственно разрешенным набором цифр. Если можно набрать число данным способом, то второй и третий способ можно не проверять.
2) i = A + (i-A), где A принадлежит интервалу [1, i-1]. Для каждого числа из этого интервала уже найден ответ. Получается, что len(i) = len(A) + 1 + len(i-A). Заметим, что размер интервала можно сократить в два раза.
Для каждого числа нужно хранить метку: получено ли данное число с помощью плюса двух арифметических выражений.
3) i = P * (i/P), где P принадлежит интервалу [2, sqrt(i)]. При этом i делится на P без остатка. len(i) = len(P) + 1 + len(i/P). Если число P было получено оптимальным способом с использованием сложения, то его арифметическое выражение при формировании числа i нужно обрамить в скобки и добавить к len(i) число 2. Аналогично нужно поступить и с числом i/P.

Последовательно перебирая все способы получения числа i указанными тремя способами находим минимальную длину арифметического выражения, которым можно получить данное число i, сохраняем полученное арифметическое выражения для дальнейшего подсчета других числе больше i
Решение

Условия задач: http://goo.gl/ApbiPW
Полный монитор: http://goo.gl/lAAkdh
Тесты: http://goo.gl/5anx35

IT-CON 2012(Фотоотчет)

Начало разбора

IT-CON 2012 (Олимпиада для студентов 3-5 курсов) Разбор + Материалы + Монитор

Условия задач

Разбор:
A. Трехзначные числа
Задачу можно решать перебором всех чисел в интервале [100,999], что дает генерацию чисел в порядке возрастания. Для каждого числа находим сумму цифр и сравниваем ее с заданной. Удовлетворяющие числа будем хранить в динамическом массиве.

Решение 1(конвертация числа в строку)
Решение 2(откусывание последней цифры числа)
Решение 3(перебор цифр)

B. Электронная почта
Задача ну умение переводить буквы латинского алфавита в нижний регистр. Пожалуй самая легкая задача олимпиады.

Решение 1(с использованием функции tolower())
Решение 2(сопоставление заглавных и прописных букв)
Решение 3(с использованием смещения)

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

Решение

D. Уникальные элементы
Самым простым решением было “загнать” все элементы в set и вывести количество элементов получившегося set’a.
В рамках другого решения можно было отсортировать массив любым известным алгоритмом сортировки, алгоритмическая сложность которого не превышала бы квадратичную. В результате можно было перебрать все пары соседних элементов и найти те из них, где текущий элемент не равен последующему. Количество таких пар + 1 является ответом на задачу.

Решение 1 (с использованием set’a)
Решение 2 (с использованием sort’a)
 
E. Сапер
Чисто техническая задача. Жизнь существенно упростит массив движений, в котором нужно записать смещения в 8 направлений:

1. ...
2. int moveX[8] = {-1,-1,-1, 0, 0, 1,1,1};
3. int moveY[8] = {-1, 0, 1,-1, 1,-1,0,1};
4. bool correct(int x, int y) {
5.   if (x < 1 || y < 1) return false;
6.   if (x > n || y > m) return false;
7.   return true;
8. }
9. ...
10. for (int p=0;p<8;++p){
11.   int x = i + moveX[p];
12.   int y = j + moveY[p];
13.   if (correct(x,y) && mas[x][y] !=-1)
14.     ++mas[x][y];
15. ...

* This source code was highlighted with Source Code Highlighter.

Решение

F. Генерация подмножеств
Классическая задача по комбинаторике.
Рассмотрим первое решение. Пусть N = 3. Рассмотрим все числа от 0 до 2^n – 1.
           123
      0 –> 000 = {}
      1 –> 001 = {3}
      2 –> 010 = {2}
      3 –> 011 = {2,3}
      4 –> 100 = {1}
      5 –> 101 = {1,3}
      6 –> 110 = {1,2}
      7 –> 111 = {1,2,3}

Решение 1 (через двоичное представление)
Решение 2 (рекурсивное с построением дерева состояний)

G. Количество нулей у факториала
Стоит заметить, что количество нулей, на которые заканчивается факториал равно количеству десяток в разложении этого факториала на множители. Десятка состоит из двух простых сомножителей. При этом множитель 5 в разложении факториала на простые множители будет встречаться намного реже, чем множитель 2. Поэтому количество нулей у факториала на конце будет равно количеству пятерок в разложении его на простые множители.

Решение 1
Решение 2

H. Язык разметки RHTML 1.0.
Можно применить один из двух подходов: конечный автомат и механизм “откусывания”.
Первый пишется дольше, но работает всегда быстрее и легко масштабируется. Второй способ пишется проще и работает чуть медленнее. Главное аккуратность и обильное тестирование.

Решение 1 (конечный автомат)
Решение 2 (с помощью “откусывания”)
Решение 3 (конечный автомат + С-строка) [Автор: Сагунов Данил]

I. Объединение прямоугольников
Единственная задача, для которой я не писал тесты, а взял оригинальные с задачника Федора Меньшикова.
Я ее уже рассматривал ранее(6D. Площадь прямоугольников)

Решение

J. Путь в матрице
Оригинальное условие задачи находится здесь: http://projecteuler.net/problem=83
Я предполагал решение задачи через алгоритм Дейкстры, но ограничения были подобраны так, что и реализация алгоритма Флойда также укладывались в отведенные лимиты. При таком подходе представляет исходную матрицу в виде графа, где каждая вершина имеет до 4 соседей. Ребро между (i,j) и (i+1,j) вершиной будет иметь вес a[i][j], где a – исходная матрица. После того как граф построен можно запускать вышеописанные алгоритмы.
Участники, сдавшие решения предложили обычный BFS на матрице. Это решение пишется намного проще.

Решение 1(алгоритм Флойда)
Решение 2(алгоритм Дейкстры)
Решение 3(BFS)


Тесты и условия задач: http://goo.gl/DvISB
Авторские решения:     http://goo.gl/lyEjn
Размороженный монитор: http://goo.gl/QOTRa

Нахождение количества компонент связности

Рассмотрим базовую задачу.
Условие:
Дан неориентированный граф G, имеющий N вершин и M ребер. Чтобы все рассмотренные подходы имели практических смысл, ограничим N<=1000.
Необходимо найти количество компонент связности данного графа.

Формат входных данных: В первой строке входного файла находятся N и M, разделенные пробелом. Далее идет M строк, содержащих пару вершин, между которыми находится ребро. Вершины нумеруются с 1.
Формат выходных данный: В единственной строке выдать количество компонент связности графа.

Пример:
input.txt
15 11
1 2
2 3
2 11
10 11
11 12
11 15
4 12
12 13
8 14
7 14
5 6
output.txt
4

Компонента связности неориентированного графа является подграф, в котором для любой пары вершин v и u существует путь. Между двумя различными компонентами связности не существует пути.

Задача стара, как мир. Но тем не менее сегодня покажу несколько подходов по ее решению.

1. Поиск в глубину(DFS)
Самое классическое решение. Даже комментировать особо нечего.

1. const int SIZE = 1e3 + 10;
2. vector<int> adj[SIZE];
3. bool usd[SIZE];
4. ...
5. void dfs(int cur) {
6.   usd[cur] = true;
7.   for (int i=0;i<adj[cur].size();++i) {
8.     int nxt = adj[cur][i];
9.     if (!usd[nxt])
10.       dfs(nxt);
11.   }
12. }
13. int connected_components_amount_dfs() {
14.   int cnt = 0;
15.   for (int i=1; i<=n; ++i) {
16.     if (!usd[i]) {
17.       dfs(i);
18.       ++cnt;
19.     }
20.   }
21.   return cnt;
22. }

* This source code was highlighted with Source Code Highlighter.

Граф храним в виде списка смежности(строка 2). Общая сложность решения $latex O(N + M)$.
Решение

2. DSU подобная структура(ленивый подход)
Будем делать конденсацию компоненты в одну вершину. Идея следующая: будем последовательно обрабатывать ребра. Каждая компонента связности будет представлена одной своей вершиной(титульная). При этом неважно какой. По ходу обработки ребер титульная вершина компонент может меняться.
В итоге для нахождения количества компонент связности нужно найти количество титульных вершин.

1. const int SIZE = 1e3 + 10;
2. int p[SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_dsu() {
6.  
7.   scanf("%d %d", &n, &m);
8.  
9.   for (int i=1;i<=n;++i) {
10.     p[i] = i;
11.   }
12.  
13.   for (int i=0;i<m;++i) {
14.     scanf("%d %d", &f, &s);
15.     int par = p[f];
16.     for (int j=1;j<=n;++j) {
17.       if (p[j] == par)
18.         p[j] = p[s];
19.     }
20.   }
21.   for (int i=1;i<=n;++i)
22.     usd[p[i]] = true;
23.   int cnt = 0;
24.   for (int i=1;i<=n;++i) {
25.     if (usd[i]) ++cnt;
26.   }
27.   return cnt;
28. }

* This source code was highlighted with Source Code Highlighter.

Заметим, что сам граф непосредственно вообще никак не хранится. Общая сложность $latex O(M*N)$ 
Решение

3. Система непересекающихся множеств (DSU)
Реализацию, представленную выше можно существенно усовершенствовать. При добавлении нового ребра будем “мерджить меньшее подмножество к большему” + сжимать пути. У emaxx’а рассматривается доказательство того, что ассимптотика обработки одного ребра равна $latex O(\alpha (N))$, где $latex \alpha (N)$ – обратная функция Аккермана.

1. const int SIZE = 1e3 + 10;
2.  
3. int p[SIZE];
4. int size[SIZE];
5.  
6. int par(int x) {
7.   return p[x] == x ? x : p[x] = par(p[x]);
8. }
9. int connected_components_amount_dsu() {
10.  
11.   scanf("%d %d", &n, &m);
12.  
13.   for (int i=1;i<=n;++i) {
14.     p[i] = i;
15.     size[i] = 1;
16.   }
17.  
18.   for (int i=0;i<m;++i) {
19.     scanf("%d %d", &f, &s);
20.     f = par(f); s = par(s);
21.     if (f != s) {
22.       if (size[f] > size[s])
23.         swap(f,s);
24.       p[f] = s;
25.       size[s] += size[f];
26.     }
27.   }
28.   bool usd[SIZE];
29.   memset(usd, 0, sizeof(usd));
30.   for (int i=1;i<=n;++i)
31.     usd[par(i)] = true;
32.   int cnt = 0;
33.   for (int i=1;i<=n;++i) {
34.     if (usd[i]) ++cnt;
35.   }
36.  
37.   return cnt;
38. }

* This source code was highlighted with Source Code Highlighter.

Как и прежде сам граф не хранится в виде матрицы смежности. Общая сложность $latex O(M * \alpha (N))$

4. Алгоритм Флойда.
Этот подход для самых ленивых, правда он требует хранить граф явно в виде матрицы смежности.
Запускаем алгоритм Флойда и строим матрицу достижимости для каждой пары вершин. В результате если первоначально adj[u][v] указывало на наличие ребра между u и v, то после работы алгоритма adj[u][v] будет указывать на наличие пути между u и v. После чего можно написать DFS двумя вложенными циклами.

1. const int SIZE = 1e3 + 10;
2. int adj[SIZE][SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_floyd() {
6.  
7.   for (int k=1;k<=n;++k){
8.     for (int i=1;i<=n;++i){
9.       for (int j=1;j<=n;++j){
10.         if (adj[i][k] + adj[k][j] == 2)    
11.           adj[i][j] = 1;
12.       }
13.     }
14.   }
15.  
16.   int cnt = 0;
17.   for (int i=1;i<=n;++i) {
18.     if (!usd[i]) {
19.       ++cnt;
20.       usd[i] = true;
21.       for (int j=1;j<=n;++j) {
22.         if (adj[i][j] && !usd[j])
23.           usd[j] = true;
24.       }
25.     }
26.   }
27.   return cnt; 
28. }

* This source code was highlighted with Source Code Highlighter.

Алгоритм ужасно долгий, но зато пишется довольно просто. Общая сложность $latex O({ N }^{ 3 }) $
Решение

Собственно пока и все. Мы рассмотрели 3 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.

Нахождение номера старшего бита числа

Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче RMQ.
Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1\leqslant{N}\leqslant{2}^{32}-1$).

1. naive [O(logN)] Первый способ самый простой и очевидный: будем сдвигать N вправо на один бит, пока оно не станет равным 1 (а не 0, так мы сэкономим одну итерацию).

1. inline int high_bit_line(UINT n) {
2.   int res = 0;
3.   while (n != 1) {
4.     n >>= 1;
5.     res++;
6.   }
7.   return res;
8. }

* This source code was highlighted with Source Code Highlighter.

Сложность первого алгоритма - количество цифр в двоичном представлении N, то есть $latex \log_2{N}$.

2. log2 [O(const)] Второй способ математический. Поскольку номер старшего бита - показатель старшей степени двойки, то его номер можно найти с помощью логарифма, округлив его вниз:

1. #include <cmath>
2.  
3. const double EPS = 1e-11;
4. inline double log2(double n) {
5.   return log(n) / log(2.0);
6. }
7. inline int high_bit_log2(UINT n) {
8.   return (int)(log2((double)n) + EPS);
9. }

* This source code was highlighted with Source Code Highlighter.

Вроде бы все классно, но могут возникнуть проблемы с округлением. Поскольку математические операции в cmath могут возвращать неточные значения (например, sqrt(4) = 1.9999...) , то приходится добавлять к их результатам константу. Константа должна быть строго меньше числа, обратного максимальному значению N, иначе это может привести к неправильному результату (например, если к $latex log_2({2}^{32}-1)$ прибавить 10^-9, то результат будет больше 31). Поэтому в нашем случае я взял 10^-11, так как $latex \frac 1 {{2}^{32}} \approx {2}*{10}^{-10}$.
К сожалению, библиотека cmath в Visual Studio не поддерживает функцию log2, поэтому пришлось делать промежуточную функцию. Сложность вычисления логарифма равна константе, но она достаточно велика.

3. Binary search [O(log(logN))] В основе этого способа лежит метод бинарного поиска. Будем брать правую часть числа (в двоичном представлении), пока она не равна нулю, а иначе берем левую часть, постепенно деля число пополам, пока не получим 1:

1. inline int high_bit_bs(UINT n){
2.   int size = sizeof(n) * 4;
3.   int res = 0;
4.   while (n != 1) {
5.     int l = n >> size;
6.     if (l) {
7.       n = l;
8.       res += size;
9.  
10.     } else {
11.       n ^= l << size;
12.     }
13.     size >>= 1;
14.   }
15.   return res;
16. }

* This source code was highlighted with Source Code Highlighter.

Рассмотрим применение этого алгоритма к числу 1234567890.

$latex 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 | 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0$ res = 0; size = 16;

$latex 0 1 0 0 1 0 0 1|1 0 0 1 0 1 1 0$ res = 16; size = 8;

$latex 0 1 0 0|1 0 0 1$ res = 24; size = 4;

$latex 0 1|0 0$ res = 28; size = 2;

$latex 0|1$ res = 30; size = 1;
Сложность этого способа равна логарифму от числа битов N, то есть $latex \log _{ 2 } (\log _{ 2 }{ N } )$.

4. Binary search with mask [O(log(log(N)))]
Да, я не ошибся, сложность четвертого алгоритма почти равна сложности третьего, так как этот способ является всего лишь небольшой оптимизацией предыдущего. В третьем алгоритме мы находим правую часть числа через левую (строка 9). Здесь мы затрачиваем две операции: битового сдвига и исключающего ИЛИ (XOR). Эти операции можно заменить на сложение и И (AND), добавив константный массив масок:

const int MASK_R[6] = {0x0000FFFF, 0x000000FF, 0x0000000F, 0x00000003, 0x00000001};

Немного исправив код третьего способа, получаем:

1. inline int high_bit_bsm(UINT n){
2.   int size = sizeof(n)*4;
3.   int res = 0;
4.   int m = 0;
5.   while (n != 1) {
6.     int l = n >> size;
7.     if (l) {
8.       n = l;
9.       res += size;
10.     } else {
11.       n &= MASK_R[m];
12.     }
13.     size >>= 1;
14.     m++;
15.   }
16.   return res;
17. }

* This source code was highlighted with Source Code Highlighter.

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

Выводы: Подход с бинарным поиском  дает наилучший результат.
Если нужно решать поставленную задачу на ограниченном диапазоне, который можно хранить в памяти, то лучше динамикой подсчитать позицию старшего единичного бита для каждого числа в диапазоне.
Эта идея хорошо описана в вики конспектах ИТМО(Раздел “Применение к задаче RMQ”).

Problem 377 [ProjectEuler.net]

 

 

 

[Условие задачи]
Решать задачу начнем с простого.
Для начала найдем $latex f(13)$. Это можно сделать несложным рекурсивно-комбинаторным алгоритмом, который оставим для самостоятельной проработки.
Итог: $latex f(13)=3835856884757$

Получить $latex f(169)$ тем же алгоритмом вряд ли получится.
Далее будет описан алгоритм, который может это сделать. Представленную логику можно применить для любой степени 13.

Введем интуитивно понятные термины:
Префикс длины L числа N – первые L цифр (старшие разряды) числа N.
Постфикс длины L числа N – последние L цифр (младшие разряды) числа N.
Сумма префикса/постфикса – сумма цифр, входящих в префикс/постфикс.
Под промежуточным числом будем понимать число, которое используется при подсчете значения $latex f({ 13 }^{ k })$, так например число 1121 является промежуточным для $latex f(5)$
По условию задачи нужно найти последние 9 цифр ответа. Минимальным постфиксом длины 9 промежуточного числа для $latex f(169)$ является 111111111, а максимальным - 999999999. Т.к. в условии оговорено, что в состав промежуточного числа не входит ноль, то можно сделать утверждение, что количество различных постфиксов длины 9 для промежуточных чисел будет ровно $latex { 9 }^{ 9 }=387 420 489$, а различных сумм заданных постфиксов $latex 81-9+1=73$.
Для фиксированного постфикса промежуточного числа найдем количество возможных префиксов. Пусть сумма постфикса равна $latex S$, тогда сумма префикса равна $latex 169-S$.
Пусть $latex G(N)$ – функция которая возвращает количество всевозможных префиксов, сумма цифр которых равна $latex N$. Остаточные знания нам навевают понятие Разбиение числа на слагаемые, но в нашем случае нужно использовать не разбиение, а Композицию числа на слагаемые.
В общем случае количество композиций числа $latex N$ на ненулевые слагаемые равно $latex { 2 }^{ N-1 }$, но это только в том случае, если нет ограничений на слагаемые. В нашем же случае каждое ненулевое слагаемое должно не превышать 9.
Для того, чтобы найти $latex G(N)$ вспомним старую задачу Зайчик. Если вникнуть, то можно увидеть, что в этой задаче как раз и ищется функция $latex G(N)$ с ограничением на максимальное слагаемое.
Получаем: $latex \displaystyle G(N)=\left\{\begin{matrix}1, N=0\\ 2^{N-1}, 1<=N<=9\\ \sum_{i=1}^{9}G(N-i), N>9\end{matrix}\right.$
Последняя формула выглядит весьма угрожающе. В интернетах находим, что $latex G(N)$ образует последовательность чисел, называемых Fibonacci 9-step numbers.
И вот наверное сейчас мы подошли к самому интересному. $latex G(169-9)$ мы еще сможем найти, а как быть если степень 13 будет велика. Нужен способ, который находит G(N) быстрее чем за O(N).
В книге “Программирование. Теоремы и задачи”(А.Шень) приводится пример, как можно найти N-ое число Фибоначчи за O(logN) с помощью быстрого возведения в степень начальной матрицы. Тот же принцип можно использовать и здесь. Приведу фрагмент, по которому можно понять общую логику:

1. typedef unsigned long long ULL;
2. const ULL OSN = (ULL)1e9;
3. const ULL BASE[SIZE][SIZE] = {
4.   {128, 64, 32, 16, 8, 4, 2, 1, 1},
5.   {64, 32, 16, 8, 4, 2, 1, 1, 0},
6.   {32, 16, 8, 4, 2, 1, 1, 0, 0},
7.   {16,  8, 4, 2, 1, 1, 0, 0, 0},
8.   {8,  4, 2, 1, 1, 0, 0, 0, 0},
9.   {4,  2, 1, 1, 0, 0, 0, 0, 0},
10.   {2,  1, 1, 0, 0, 0, 0, 0, 0},
11.   {1,  1, 0, 0, 0, 0, 0, 0, 0},
12.   {1,  0, 0, 0, 0, 0, 0, 0, 0}
13. };
14. const ULL A[SIZE][SIZE] = {
15.   {1, 1, 0, 0, 0, 0, 0, 0, 0},
16.   {1, 0, 1, 0, 0, 0, 0, 0, 0},
17.   {1, 0, 0, 1, 0, 0, 0, 0, 0},
18.   {1, 0, 0, 0, 1, 0, 0, 0, 0},
19.   {1, 0, 0, 0, 0, 1, 0, 0, 0},
20.   {1, 0, 0, 0, 0, 0, 1, 0, 0},
21.   {1, 0, 0, 0, 0, 0, 0, 1, 0},
22.   {1, 0, 0, 0, 0, 0, 0, 0, 1},
23.   {1, 0, 0, 0, 0, 0, 0, 0, 0}
24. };
25. const ULL E[SIZE][SIZE] = {
26.   {1, 0, 0, 0, 0, 0, 0, 0, 0},
27.   {0, 1, 0, 0, 0, 0, 0, 0, 0},
28.   {0, 0, 1, 0, 0, 0, 0, 0, 0},
29.   {0, 0, 0, 1, 0, 0, 0, 0, 0},
30.   {0, 0, 0, 0, 1, 0, 0, 0, 0},
31.   {0, 0, 0, 0, 0, 1, 0, 0, 0},
32.   {0, 0, 0, 0, 0, 0, 1, 0, 0},
33.   {0, 0, 0, 0, 0, 0, 0, 1, 0},
34.   {0, 0, 0, 0, 0, 0, 0, 0, 1}
35. };
36. ULL G(ULL n) {
37.   ULL res = 0;
38.   if (n <= 9) {
39.     res = _pow(2, n - 1);
40.   }
41.   else {
42.     matrix AN = E, cur = A;
43.     n -= SIZE - 2;
44.     while (n) {
45.       if (n & 1)
46.         AN = AN * cur;
47.       cur = cur * cur;
48.       n >>= 1;
49.     }
50.     matrix fin = matrix(BASE) * AN;
51.     res = fin.data[0][1];
52.   }
53.   return res;
54. }

* This source code was highlighted with Source Code Highlighter.

Все нужные кирпичики описаны. Теперь соберем их в общую картину. 
Последние 9 цифр суммы всех промежуточных чисел для $latex f(169)$ c фиксированным постфиксом можно найти по формуле: $latex postfix*G(169-sum(postfix))mod1e9$. Перебрав все возможные постфиксы можно найти и само значение $latex f(169)$. Для всех остальных степеней 13, как уже говорилось ранее, применима такая же логика. 
Можно предложить несколько схем, ускоряющих общие вычисления. Но их мы оставим для самостоятельной проработки.

Расстановка знаков в арифметическом выражении

[Все темы по размещениям]

Задача: 155. Дешифровка выражения(contester.tsure.ru) [Условие]
Предварительные темы:    [Генерация всех размещений с повторениями рекурсивным способом]
                         [Генерация следующего размещения с повторениями]
                         [Подсчет арифметического выражения(обратная польская нотация)]
Дополнительная практика: Задачи для подсчета арифметического выражения (см. занятие 4 - архив)

Итак, имеется корректное арифметическое выражение вида (9?8)?(0?3)?2=-25, вместо знаков ? необходимо поставить одну из 4 операций +,-,*,/ так, чтобы выражение стало правильным. Если такого сделать нельзя, то нужно вывести “No solution.”. Для удобства гарантируется, что в левой части выражения все числа являются цифрами и отсутствуют унарные знаки. В правой же части может быть любое число по модулю не превышающее 10¹⁵.

Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10
Алфавит знаков содержит четыре элемент: {+,-,/,*}.
Количество позиций в размещении(количество знаков ? в выражении): 2
Общее количество размещений: 4²=16

Сгенерируем все размещения с повторениями рекурсивным способом и получим все возможные комбинации исходного арифметического выражения:

1. 2+(3+4)=9
2. 2+(3-4)=1
3. 2+(3*4)=14
4. 2+(3/4)=2
5. 2-(3+4)=-5
6. 2-(3-4)=3
7. 2-(3*4)=-10
8. 2-(3/4)=2
9. 2*(3+4)=14
10. 2*(3-4)=-2
11. 2*(3*4)=24
12. 2*(3/4)=0
13. 2/(3+4)=0
14. 2/(3-4)=-2
15. 2/(3*4)=0
16. 2/(3/4)=NAN

* This source code was highlighted with Source Code Highlighter.

Значение NAN обозначает, что в выражении присутствует деление на ноль. Сам подсчет будем делать с помощью перевода в обратную польскую запись, подсчетом значения на лету.
Подсчет значения на лету можно сделать так:

1. string opers = "+-*/";
2. bool calc(INT &f, INT &s, char op, INT &res) {
3.   switch(op) {
4.     case '+' : res = f + s; return true;
5.     case '-' : res = f - s; return true;
6.     case '*' : res = f * s; return true;
7.     case '/' : if (s != 0) {
8.             res = f / s;
9.             return true;
10.           }
11.           return false;
12.   }
13.   return false;
14. }
15. bool calc_last (stack<INT> &val, stack<char> &oper) {
16.   INT s = val.top(); val.pop();
17.   INT f = val.top(); val.pop();
18.   INT r = -1;
19.   if (calc(f,s,oper.top(),r)) {
20.     val.push(r);
21.     oper.pop();
22.     return true;
23.   }
24.   return false;
25. }
26. int prior(char op) {
27.   switch(op) {
28.     case '+':
29.     case '-': return 0;
30.     case '*':
31.     case '/': return 1;
32.   }
33.   return -1;
34. }
35. bool is_num(char c) {
36.   return '0' <= c && c <= '9';
37. }
38. bool calc(const string &expr, INT &res) {
39.   stack<INT> val;
40.   stack<char> oper;
41.   for (int i=0;i<expr.size();++i) {
42.     if (is_num(expr[i]))
43.       val.push(expr[i] - '0');
44.     else if (expr[i] =='(')
45.       oper.push(expr[i]);
46.     else if (expr[i] == ')') {
47.       while (oper.top() != '(') {
48.         if (!calc_last(val, oper))
49.           return false;
50.       }
51.       oper.pop();
52.     }
53.     else { // expr[i] - операция
54.       while (!oper.empty()) {
55.         if (prior(oper.top()) >= prior(expr[i])) {
56.           if (!calc_last(val, oper))
57.             return false;
58.         }
59.         else break;
60.       }
61.       oper.push(expr[i]);
62.     }
63.   }
64.   while (!oper.empty()) {
65.     if (!calc_last(val,oper))
66.       return false;
67.   }
68.   res = val.top();
69.   return true;
70. }

* This source code was highlighted with Source Code Highlighter.

Исходный код: здесь

Отправляем в систему проверки на contester.tsure.ru и получаем вердикт: TLE9. =))
В худшем случае количество операций равно 10, значит общее количество генерируемых размещений будет 4¹⁰=1048576. Получается, что приведенный фрагмент кода подсчета значения выражения на лету будет запускаться более 1 млн. раз. Т.к. в данной задаче нам придется генерировать все размещения, то естественным путем оптимизации исходного решения – минимизировать количество построений обратной польской записи.
Рассмотрим несколько выражений и их обратные польские записи.

Номер     Выражение           Обратная польская запись
1         5*2+3-(7+2)/2       5 2 * 3 + 7 2 + 2 / -
2         5/2-3+(7-2)*2       5 2 / 3 – 7 2 – 2 * + 
3         5+2*3/(7*2)-2       5 2 3 * 7 2 * / + 2 -
4         5-2/3*(7/2)+2       5 2 3 / 7 2 / * – 2 +

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

Поэтому изначально можно сгенерировать до 2¹⁰=1024 размещений из приоритетов [0 и 1]. При этом, если на место операции выпадает 0 в размещении это говорит о том, что на ее место будут последовательно поставлены операции с нулевым приоритетом, т.е + или –.
Для выражений с одинаковыми размещениями приоритетов получаются подобные обратные польские записи.

Рассмотрим выражение:              5?2?3?(7?2)?2
Текущее размещение из приоритетов: {1, 0, 0, 0, 1} 
Обратная польская запись:          5 2 [1] 3 [0] 7 2 [0] 2 [1] [0], где [x] – операция с приоритетом x
Как можно заметить, текущая обратная польская запись соответствует 1 и 2 выражению из таблицы.

Далее подумаем, как можно перебрать конкретные знаки, с уже расставленными приоритетами операций.
Для текущего размещения R можно поставить в соответствие два размещения F и S.
При этом длина F равна количеству нулей в размещении R, а длина S – количеству единиц.
Элементы множества F будут состоять из операций с нулевым приоритетом, а S – из элементом с единичным приоритетом.

Номер   Выражение        R              F           S
1       5*2+3-(7+2)/2    {1,0,0,0,1}    {+,-,+}     {*,/}
2       5/2-3+(7-2)*2    {1,0,0,0,1}    {-,+,-}     {/,*}
3       5+2*3/(7*2)-2    {0,1,1,1,0}    {+,-}       {*,/,*}
4       5-2/3*(7/2)+2    {0,1,1,1,0}    {-,+}       {/,*,/}

Все вышеизложенную идею можно описать так. При этом получается, что в худшем случае придется генерировать 2¹⁰=1024 обратных польских записей вместо 4¹⁰=1048576. Благодаря этим преобразованием последнее решение уложилось в 1.5 секунды на сервере проверки.

В целях рефакторинга второй реализации можно скрестить генерацию размещений R и {F,S}.

Получение номера по размещению с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Ранее мы научились генерировать размещение с повторениями по номеру. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему.

Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке.
20221112₃=2*2187+0*729+2*243+2*81+1*27+1*9+1*3+2*1=4374+486+162+27+9+3+2=5063₁₀.

Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064.

1. typedef unsigned long long ULL;
2. ULL get_num_by_placement_rep(const vector<int> &cur, int n, int k) {
3.   ULL num = 0;
4.   ULL step = 1;
5.   for (int i=cur.size()-1;i>=0;--i) {
6.     num += cur[i] * step;
7.     step *= k;
8.   }
9.   return num;
10. }

* This source code was highlighted with Source Code Highlighter.

Генерация размещения с повторениями по номеру

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: [82. Все строки длины n из k различных символов]

Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке.
Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания.
Проверим наше утверждение на размещении “31”: 31₄=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0.
Данная логика отображена в следующей функции:

1. typedef unsigned long long ULL;
2. void gen_placement_rep_by_num(vector<int> &cur, ULL num, int n, int k) {
3.   cur.assign(n,0);
4.   int pos = n - 1;
5.   while (num) {
6.     cur[pos--] = num % k;
7.     num /= k;
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.

Генерация следующего и предыдущего размещения с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке.

R_i = {1, 5, 6, 4, 6}; n = 5; k = 7
R_i+1 = {1, 5, 6, 5, 0}

Для генерации следующего размещения будем пользоваться простым правилом:
Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.

1. bool next_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos>=0 && r) {
5.     cur[pos]++;
6.     r = cur[pos] == k;
7.     if (r) cur[pos] = 0;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация предыдущего размещения делается по аналогичной схеме:

1. bool prev_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos >=0 && r) {
5.     cur[pos]--;
6.     r = cur[pos] == -1;
7.     if (r) cur[pos] = k-1;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Генерация всех размещений с повторениями рекурсивным способом

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: Все строки длины n из k различных символов

Пусть задан алфавит из K первых цифр, начиная с 0. Необходимо сгенерировать все размещения с повторениями длины N для элементов данного алфавита. Другими словами для N = 2 и K = 4 получаем:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Генерация такой последовательности не должно составить большого труда:

1. void gen(int pos) {
2.   if (pos == n) {
3.     for (int i=0;i<n;++i)
4.       printf("%d",cur[i]);
5.     printf("\n");
6.     return;
7.   }
8.   for (int i=0;i<k;++i) {
9.     cur[pos] = i;
10.     gen(pos+1);
11.   }
12. }

* This source code was highlighted with Source Code Highlighter.

Изначально функция gen запускается с параметром 0.
Полное решение: здесь