ACM ICPC NEERC 2012. Контест, закрытие, материалы.

Контест для нас проходил по стандартной схеме для Питера - я пишу шаблончик, Антон и Иван читают условия.

ACM ICPC NEERC 2012. День второй

Наступил второй день данного мероприятия.

ACM ICPC NEERC 2012. День первый.

Сегодня (30 ноября) команда Vologda SPU + тренер прибыли в Санкт Петербург на место проведения ACM ICPC NEERC 2012.

Рыбинск'12 или последний шанс для Vologda SPU 1

Доброго времени суток!

Несмотря на то, что с четвертьфинала центрального региона 2012 прошло уже прилично времени, воспоминания о нём всё ещё живы в памяти и я решил поделиться ими.
Хотелось бы предупредить, что в посте присутствует много информации, которая не относится непосредственно к сабжу, но которую я посчитал важной для упоминания на случай, если кому-то пригодится подобный опыт подготовки к соревнованиям, ну и немного лирики :-) Если вам это не интересно — смело пропускайте первые 2 заголовка.

Обзор S4RiS StanD на Codeforces.ru

Оно свершилось!
Сегодня я нашёл в себе силы и время написать обзор последней версии StanD на Codeforces.
Обзор получился весьма полным и добротным.
Первые комментарии и "плюсики" говорят о весьма удачном начале.
Посмотрим, что будет дальше.

Что было в сентябре.

Мои действия в сентябре можно было бы сформулировать тремя словами - "Работа. Учёба. StanD".

Rybinsk 3 Days Rush #4

Вот и подошла к концу очередная 3-ёх дневная тренировка.

Как стал замечать - задачи решаются всё лучше и лучше, но вот решать каждый день сил всё меньше и меньше. Видимо сказывается усталость от работы. Я уже договорился об отпуске на неделю когда будет проходить Рыбинск (16-18 октября). Учитывая учебную занятость и возможные командные тренировки по выходным, кажется разумной идеей в октябре чуток сбавить темп, чтобы не перегореть перед соревнованием.

В августе я пытался сконцентироваться на реализационных задачах, ДП, жадности. В сентябре я хотел бы уделить максимум решению задач на структуры данных. Буду так же сортировать задачи с архива Codeforces и решать. Параллельно командой предпринимаются активные действия чтобы быть готовыми сменить язык решений на самом соревновании.

И так, решенные задачи:

Командная тренировка 01.09.2012.

Сегодня была проведена последняя (5ая) летняя тренировка команды
Vologda SPU #1.
В качестве проблемсета был выбрал ВКОШП 2008.

Во время соревнования команда сдала 6/10 задач +1 задача была сдана в дорешивании.
В общем, можно считать, что тренировка прошла вполне успешно.
Я сегодня написал 5 из 7 задач.

Данный проблемсет мне очень понравился.
Весьма сбалансированный, затрагивает разные темы. Подробнее о задачах будет написано в очередном посте "Rybinsk 3 Days Rush".
Контест рекомендую для решения для не топовых команд.

Т.к. начинается учебный год, а мои тиммейты будут учиться практически всю субботу - пока предложение было в том, чтобы проводить тренировки по воскресеньям. А в субботу я буду ходить на курсы по C++ :-)

В оставшееся время планируется командные решения задач с 1/4 Южного четвертьфинала на сайте SGU.

Rybinsk 3 Days Rush #3

Следующий раш начался 28.08.
Начало было ужасным...

Rybinsk 3 Days Rush #2.

Из-за повышенной загруженности на работе взял себе перерыв на четверг.
В пятницу возобновил решение задач.
Решил, что буду ставить значки * перед названиями задач, которые мне очень понравились либо самим решением, либо получил некий крайне полезный опыт. Может и кто другой оценит.
Итак, решенные задачи:

Командная тренировка 26.08.2012.

В последнее воскресенье августа была проведена 4-ая командная летняя тренировка.
В составе опять замена Антона Серкова на Егора Стрешнева из-за продолжающегося отпуска первого :-)
Судя по всему, ВГПУ решили перенести 1 сентября на 3 число и в результате появляется возможность провести последнюю тренировку у меня дома в следующие выходные уже стандартным составом.
Для решения был выбран комплект задач ВКОШП 2007.

Rybinsk 3 Days Rush #1.

Как было анонсировано ранее я планировал устраивать тренировки продолжительностью в 3 дня по 10 задач с CF по тегам, описанным в предыдущем посте.
Для конспирации назовём это "Rybinsk 3 Days Rush" :-)
Итак, первые итоги.

Мысли вслух. Поступление в магистратуру. Что решать к Рыбинску.

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

Командная тренировка 19.08.2012

Сегодня была проведена очередная тренировка.
Из-за отбывшего в отпуск (и видимо из России) Антона Серкова к нам присоединился участник второй команды ВГПУ - Стрешнев Егор.
Я боялся, что тренировка получится не совсем полноценная, но оказалось совсем наоборот.
Егор удачно влился в коллектив и решил 2 задачи.
В итоге команда решила всего 4 задачи с не плохим штрафом и заняла виртуальное 54-е место в ВКОШП 2006.

Наблюдается не хорошая тенденция что команде не поддаются нормально adhoc-задачи среднего уровня и ДП среднего уровня. Надо над этим поработать.

Командная тренировка 11.08.2012

Сегодня была проведена очередная командная тренировка.

Проблемсет был взят с ВКОШП 2005.

В итоге команда заняла 37/126 место с 5ю задачами из 10.
Интересно, что я так и не смог придумать внятного алгоритма на задачу C(что то сильно смахивающее на топологическую сортировку с ДП), которую решило 61 команда, но придумал решение для задачи B, которую решило всего 12 команд. Будем разбираться.

Тактических ошибок замечено не было. Все по-максимуму были заняты тем, чем надо.

Так же сегодня продолжил изучать суффиксные автоматы.
Тема очень благодатная.
Есть сильные подозрения, что данный алгоритм позволит сдать сразу 3 задачи с Тимуса.
Но в задаче 1590. Шифр Бэкона напоролся на проблему того, что построить автомат не проблема.
Проблема посчитать количество различных путей в ацикличном ориентированном графе.
Очевидное рекурсивное решение дохнет уже на строке в 4000 символов или TL'ится.
Переписанное итеративное решение с 3мя стэками не может справиться уже с 3000.
В общем, в воскресенье попробую продолжить решение данных задач и окончательно разобраться в этих автоматах.

SnarkNews Summer Series-2012, Round 3

Сегодня решил написать очередной раунд серии.

В итоге решил только 1/6 задач :-(

В одной не заметил больших ограничений но начал писать, ещё одну просто не прочитал, хотя там весьма классическая известная задача.

Как минимум ещё 2-3 задачи можно попробовать дорешать, чем и займусь в до конца недели.

Это, наверно, второй по сложности раунд из первых трёх.

Командная тренировка 04.08.2012

Сегодня у команды Vologda SPU #1 прошла полная 5и часовая тренировка.

В качестве проблемсета был взят ВКОШП 2004, размещённый в рамках проекта Codeforces - Тренировки.
В результате было решено 4 из 10 задач.
В режиме дорешивания было определено, что ещё в одной задаче ( которая не зашла) в вводе присутствовал "мусор", которого по условию быть не должно.
А в общем, эта была бы 5-ой задачей.
В общем, тренировку можно оценить на "хорошо".
Виртуальное место среди участников onsite и других виртуальных участников - 42/130

Остальные задачи соревнования буду дорешивать сам в ближайшие дни.
Следующая (и ,наверно, последняя за август) тренировка намечена на следующую неделю.

SnarkNews Summer Series-2012, Round 2

Сегодня решил написать второй раунд серии.

И честно скажу - это наверно лучший контест, который я когда либо писал :-)
Очень понравилось то, что были задачи на "немного подумать и написать", одна задача потребовала освежить в памяти одну классическую структуру, которую я без проблем написал по памяти и чисто сдал. Решил  4 из 6 задач. На пятую тупо не хватило времени написать.
В общем, 1.20 минут весьма активного решения (без "капец что и делать") и программирования.
Контест крайне рекомендуется для решения.

Неделя теории чисел.

На соревновании SNSS 2012 Round 1 была одна задача по теории чисел.
К сожалению, никаких адекватных идей в первое время не придумалось и осознавая, что мои знания в этой области ну совсем скудные (особенно что касается модулярной арифметики в широком смысле), было решено почитать Кормена.

Материалы подготовки.

В промежутках между работой, сном и отчаянными попытками затолкать задачи в SNSS2012 Round 1 на сайте e-maxx обнаружил интересную книгу -
Долинский. Решение сложных и олимпиадных задач по программированию.
Хорошо, сложные задачи. Первая тема - "Максимальный поток". ОМГ.

SnarkNews Summer Series-2012, Round 1

Стартовал SnarkNews Summer Series-2012, Round 1.
Продолжительность - 1.20.

Мне таки удалось восстановить учётку к этому ресурсу и я принял участие в виртуальном соревновании.

Решил одну задачу на ДП, вторую выбрал задачу на математику, но увы за отведённое время не справился. Будем участвовать в дорешивании.

Выбираем интересующие темы. Разное.

Ну и в заключении стоит несомненно упомянуть про всякие интересные статьи по алгебре с e-maxx, комбинаторике, теории игр.

Выбираем интересующие темы. Динамическое программирование.

Ну и на закуску стоит вспомнить о теме, без которой современное олимпиадное программирование сложно представить - динамическое программирование.

Выбираем интересующие темы. Графы.

Графы - это наверно одна из продвинутых тем, которая встречается практически на любом контесте. Материалы по этой теме наверно стоит разделить на чисто лекционные и практические. В ifmo wiki этой теме посвещен целый семестр. Так как матеарила слишком много - постараюсь выделить основные темы.

Выбираем интересующие темы. Строки и всё, что с ними связано.

Продолжаем разговор.

Одной из тем, которую я касался за эти годы реже всего - это строковые алгоритмы. Кроме поиска палиндромов, КМП ничего не писал. Думаю пришло время закрывать этот важный пробел. Тем более часто видел задачи, которые судя по отзывам решаются суффиксными структурами.

Выбираем интересующие темы. Структуры данных

В данном посте попробую описать список тем, которые хотелось бы разобрать в рамках подготовки, расставить приоритеты для изучения.

Структуры данных:

1. Дерево отрезков (SQRT-декомпозиция, классическое, дерево Фенвика).
2. Декартово дерево (обычное, по неявному ключу).
3. Система непересекающихся множеств (DSU - Disjoined Set Union).

Что мы имеем на данный момент...

Попробую провести самоанализ своих "успехов" :-)

Имеем:

• На данный момент мы имеем человека, который на 2-3 курсе старался активно заниматься решением олимпиадных задач с архива Тимуса в offline (то есть решать не в рамках реальных или виртуальных соревнований, а спокойного решения). 
• Уровень знания английского вполне позволяет не испытывать серьёзных проблем при переводе задач.
• Далеко не такая хорошая мат. база, которую крайне желательно иметь олимпиадникам.

Хочется:

• Подготовиться к успешному (а судя по epic fail выступлению всех команд центрального региона на полуфинале в Питер в следующем году поедет около 4 команд и это должны быть только реально сильные команды из имеющихся) выступлению на четвертьфинальных соревнованиях центрального региона NEERC. Войти в Top 3 :-)
• В случае выполнения  - продолжить участие в других соревнованиях (не только студенческих) по программированию для достижения успехов и там.

Первый пост блога

Всем доброе время суток.

Меня зовут Стрекаловский Олег, живу в Вологде.
В данный момент я являюсь выпускником   (покойся с миром) специалитета  факультета Прикладной математики и компьютерных технологий Вологодского ГПУ.

Мои увлечения:

• Профессиональное программирование на JavaEE(SE),
• Олимпиадны по программированию
• Поддержка моего дипломного проекта "S4RiS".

Этим летом я планирую поступать в магистратуру на том же факультете и соответственно у меня будет последняя попытка достойно выступить с командой в ACM ICPC.

С учётом этого, в данном блоге я буду писать в первую очередь о первостепенной задаче на лето - подготовке к этому соревнованию.