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