Олимпиада 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 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.