Олимпиада 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 место в общем зачете