пятница, 23 января 2015 г.

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

4 комментария:

  1. А эти задачи на каких-то проверяющих системах случайно не выложены? Просто хочется порешать и проверить верность своего решения :)

    ОтветитьУдалить
    Ответы
    1. Какие-то наверняка найти можно. Тесты и чекеры на которых проводился контест находится в архиве по ссылке: http://goo.gl/QwmEee
      Но для этого нужно локально установить систему Contester: http://www.contester.ru/
      и загрузить в нее задачи из архива.

      Если интересует какая-то конкретная задача - спрашивайте, возможно сможем найти

      Удалить
  2. In this manner my colleague Wesley Virgin's adventure begins in this SHOCKING and controversial video.

    As a matter of fact, Wesley was in the army-and soon after leaving-he found hidden, "SELF MIND CONTROL" secrets that the government and others used to get everything they want.

    THESE are the EXACT same methods lots of famous people (especially those who "come out of nowhere") and the greatest business people used to become rich and famous.

    You probably know how you only use 10% of your brain.

    Mostly, that's because the majority of your brainpower is UNCONSCIOUS.

    Perhaps this thought has even taken place INSIDE your own head... as it did in my good friend Wesley Virgin's head 7 years back, while driving an unregistered, garbage bucket of a car without a license and in his bank account.

    "I'm very fed up with living paycheck to paycheck! Why can't I turn myself successful?"

    You've taken part in those questions, am I right?

    Your very own success story is waiting to start. You just have to take a leap of faith in YOURSELF.

    UNLOCK YOUR SECRET BRAINPOWER

    ОтветитьУдалить
  3. Your Affiliate Money Making Machine is waiting -

    Plus, making money online using it is as easy as 1, 2, 3!

    It's super easy how it works...

    STEP 1. Tell the system which affiliate products the system will push
    STEP 2. Add some PUSH BUTTON traffic (it LITERALLY takes 2 minutes)
    STEP 3. Watch the system grow your list and sell your affiliate products all on it's own!

    So, do you want to start making profits???

    You can test-drive the system for yourself risk free...

    ОтветитьУдалить