arti
Записей (70), комментариев (0)
Нет информации об авторе
Записи автора arti
Расписание контестов в формате iCalendar
4
Достаточно давно Улан Дегенбаев предложил экспортировать расписание соревнований на http://olympiads.kz в формате, понятном для Google Calendar, а сейчас я нашел время воплотить эту идею на практике: http://olympiads.kz/schedule.ics.
Как пользоваться:
- открываем Google Calendar;
- выбираем Add -> Add by URL;
- вводим http://olympiads.kz/schedule.ics в поле Public Calendar Address и нажимаем Add.
Конечно использовать можно не только в Google Calendar, но и в любом органайзере, поддерживающем импорт формата iCalendar.
Работает в тестовом режиме, если заметите ошибки – сообщайте.
Олимпиады по программированию – они такие разные… Часть 4
0Последняя статья об известных мне соревнованиях по программированию.
Долгое время ACM ICPC был единственным крупномасштабным официальным соревнованием. Однако несколько лет назад ситуация изменилась: ежегодно стал проводиться Открытый Кубок по программированию. Участвовать здесь могут все, но подавляющее большинство участников – представители СНГ. Спонсоры: Яндекс и CBOSS.
Это соревнование по правилам ICPC, однако имеются некоторые отличия. Кубок проводится в течение учебного года в несколько этапов (в последнем их было 10), причем в каждом этапе могут участвовать все, независимо от результатов предыдущих этапов. Начинать участвовать можно с любого этапа. По результатам этапов командам начисляются очки, которые затем суммируются и добавляются в общий рейтинг.
Сам?ау – Вручение дипломов по-политеховски
4Сегодня, 20 июня, в КазНТУ прошла церемония вручения дипломов с отличием, или, как ее у нас (или уже у них) называют – Сам?ау. Все прошло во знакомом многим стиле «для галочки», главным образом характеризующимся полным отсутствием внимания к мелочам.
Начнем с приветствия выпускникам-отличникам, крутящегося на плазменных телевизорах в корпусах, а затем и на сцене. Эффект от небрежно слепленной в PowerPoint презентации дополняло изумительно подобранное сочетание красного текста на синем фоне. Данное сочетание, кстати, встречалось и далее по ходу церемонии.
Доверяй, но проверяй
0
Перед редизайном просматривал разные блоги и нашел интересный плагинчик от Антона Лобовкина – Одна кнопка. И все бы в нем хорошо, но, поставив себе, обнаружил неисправность – на странице с несколькими постами нажатие на кнопку под любым из постов приводит к добавлению в закладки последнего поста на странице. Сначала, как обычно, подумал, что баг где-то у меня, все-таки тему для WordPress в первый раз делал и т.п. Но, как оказалось, баг в самом плагине. Причем, что самое интересное, баг проявляется на всех сайтах, которые я видел, то есть разработчики сайтов настолько доверяют разработчикам плагинов, что даже неудосаживаются проверить базовую функциональность, из-за чего впоследствии страдают пользователи.
Отписал автору, посмотрим, может что-нибудь сделает, а пока такой баг-фикс:
- копируем ok3.utf8.js себе, если раньше этого не сделали, и в ok3.php соответствующим образом изменяем путь подключения скрипта;
- находим в нем строку html+=’<a href=»‘+this.url(i+1)+…;
- убираем из нее вызов обработчика onclick.
Дополнительные плюсы:
- скрипт будет грузиться с вашего сервера – меньше нагрузки на odnaknopka.ru и меньше время ожидания пользователя;
- при нажатии на ссылку не будет захода на odnaknopka.ru – у автора немного уменьшится статистика, но пользователю будет гораздо удобнее.
И еще одна недоработка. Скрипт подключается каждый раз при выводе ссылок на закладки, что, когда много постов, не очень хорошо. Выход переносе кода добавления скрипта в head (для чего меняем ok3.php).
P.S. Автор на своем сайте сказал, что код можно изменять при условии оставления ссылки на odnaknopka.ru, а также сам рекомендует хостить ok3.utf8.js у себя на сайте, так что все законно 
TopCoder – все, что вы хотели узнать, но боялись спросить…
0Продолжаю описывать известные мне соревнования по программированию. На этот раз – не только по спортивному программированию, но и по разработке программного обеспечения и графическому дизайну.
Пролог
Про TopCoder я случайно узнал в далеком 2005 году. Зашел на сайт, зарегистрировался, стал еженедельно получать email’ы с анонсом каких-то SRM’ов с призовым фондом $5000, но так и не решился поучаствовать – думал, нереально какому-то самоучке состязаться с профессионалами и еще претендовать на денежное вознаграждение. На участие сподвигнул меня Андрей Лопатин – двукратный чемпион мира по версии ACM ICPC, приехавший в Алматы в качестве тренера на школьные сборы в мае 2006. С тех пор я участвую почти в каждом Rated Event в секции Algorithm и ничуть не жалею об этом, даже если «сливаю» матч вчистую. Из материального заработал я немного – всего $523, которые при вычете налогов сильно уменьшаются в размере, несколько футболок и почти бесполезных вещиц. Но неоценим нематериальный вклад: возможность вживую пообщаться с легендарными личностями, посмотреть, как пишут программы профессионалы, шанс быть принятым на работу в известную компанию, ну и просто наслаждение и польза от самого процесса.
Олимпиады по программированию – они такие разные… Часть 2
0В этой части попытаюсь начать разбираться с первой причиной малораспространенности олимпийского движения в Казахстане – неведеньем. Для начала рассмотрим IOI, Республиканскую студенческую олимпиаду и ACM ICPC.
Международная олимпиада по информатике (International Olympiad in Informatics, IOI) – самое известное соревнование среди школьников.
Про схему проведения можно почитать в Википедии.
В Казахстане для участия в IOI нужно пройти достаточно жесткий (местами довольно странный) отбор по следующей схеме:
- внутришкольная олимпиада (часто формальная, но все же есть);
- районная олимпиада;
- областная (городская для городов Алматы и Астана);
- отбор на Республиканскую олимпиаду;
- Республиканская олимпиада;
- отбор на IOI.
Олимпиады по программированию – они такие разные…
0Пролог. Написал я как-то вечерком очередной SRM и подумал, а почему же так мало народу с Казахстана там участвует? Одна из причин – неведенье. С ней разберемся попозже. Ну а сейчас вторая…
Среди многих программистов (и не только) бытует такое мнение, что соревнования по программированию – совершенно никчемная трата времени. Почему же в то же время они с удовольствием занимаются каким-либо видом спорта или хотя бы делают зарядку по утрам (что не является ни чем иным, как бессмысленным передвижением белковой массы по некоторой иногда определенной, иногда хаотичной траектории)?
Да, правильно, во-первых, для большинства занятие спортом – это, прежде всего, способ поддерживать свое тело в форме. Во-вторых (хотя не все себе в этом признаются), часто занятия спортом носят состязательный характер, начиная от очевидных (футбол, бег), заканчивая не вполне очевидными (фитнес?), а стремление быть лучше хоть в чем-то присутствует почти у каждого человека.
Но ведь оба этих момента присутствуют и в соревнованиях по программированию! Ведь участие в олимпиаде или подготовка к ней независимо от результатов позволяет поддерживать в форме то, что никаким спортом не получится, – мышление. Еще Ломоносов говорил: «Математику затем учить следует, что она ум в порядок приводит», а программирование (или информатику, если угодно) можно назвать близким родственником математики. Ну а про состязательный момент даже рассказывать не стоит – достаточно разок поучаствовать в TopCoder SRM и все станет ясно
Даже руководители таких крупных компаний и организаций как Google, IBM, NSA, Yandex понимают, что программист, добившийся некоторых успехов на олимпиадах, в большинстве случаев будет ценным сотрудником. Мало того, что они спонсируют эти мероприятия, так еще ходили слухи, что в одну из крупных фирм без собеседования принимают тех, у кого рейтинг на TopCoder выше определенного значения.
Кроме таких очевидно-прагматичных причин, существует еще как минимум одна – это знакомство и общение с лучшими в своей области специалистами. Где еще можно обсудить свои идеи или баги с 20 заинтересованными в этом людьми из разных стран от Китая до ЮАР, кроме как в комнате арены после SRM’а ?
Итак, просуммируем вышесказанное. Причины заниматься спортивным программированием:
- здоровый сон во время контеста;
- развитие алгоритмического и других видов мышления;
- соревновательность;
- расширение знаний алгоритмов, структур данных, приемов и т.д.;
- знакомство с интересными людьми.
И, наконец, даже если вам не нравится писать код, если вы проектировщик, тестер или дизайнер, существуют соревнования по проектированию, разработке, тестированию и графическому дизайну.
В следующих статьях я попытаюсь осветить известные мне соревнования по программированию у нас и зарубежом, их особенности, положительные (и не очень) стороны с моей, сугубо личной, точки зрения.
Разбор задач Kazakhstan Contest 2
4Ну, как всегда, первый блин комом 
В задаче F под конец контеста обнаружился бажный тест, который, наверное, порядком попортил нервы Ренату Муллаханову и Арсению Алексееву. Приношу свои извинения – недоглядел.
Поздравляю победителя Рената Муллаханова, решившего все 7 задач.
Спасибо всем, кто поучаствовал, а также большое спасибо Улану Дегенбаеву, все отлично организовавшему.
Kazakhstan Contest 2
07-го июня после долгого устранения технических неполадок наконец-то состоится Kazakhstan Contest 2 на сервере КРСУ. Это будет, вроде бы, первый ACM-контест, почти полностью написанный мной. Так что приглашаю всех желающих, вдруг кому-нибудь даже понравится
И спасибо ребятам из КРСУ, в частности Улану Дегенбаеву и Андрею Мохову за то, что уже второй раз согласились хостить предложенный мной контест.
Краткий обзор задач Универсиады Алтая 2008
0Еще один контест, на котором удалось продемонстрировать тупость упорство: одна задача с 23-й попытки, другая с 17-й
Задача A. Сарафан для призрака датского короля
В задаче может быть 2 случая:
- обе точки на одной прямой;
- точки на разных прямых.
Первый случай тривиален, во втором надо найти точку пересечения этих прямых (если они пересекаются) и вывести суммарное расстояние от исходных точек до нее.
Для работы с прямыми удобно представить прямые в параметрических уравнениях, а находить точки пересечения можно, пересекая проекции прямых на плоскости координат, приводя таким образом задачу к двумерному виду.
Задача B. Лаэрт в затруднении
Условие сводится к нахождению максимального паросочетания в дереве. Задачу можно решить жадно или, для уверенности , динамикой. Для каждой вершины подвешенного дерева будем хранить два значения: величину максимального паросочетания в поддереве этой вершины и величину максимального паросочетания в поддереве вершины, если сама вершина участвовать в паросочетании не может.
Задача C. Загадка Горацио
Классическая задача о нахождении лексикографически минимального циклического сдвига. Для решения можно использовать алгоритмы разложения строки на простые подстроки (алгоритмы Дюваля, Линдона) или суффиксное дерево / автомат.
Задача D. Два могильщика
Скорее всего какой-то перебор, возможно с отсечениями .
Задача E. Полоний и его коллекция
Решение от одного из авторов:
«научимся для тождественной перестановки длины 6 получать все 5 перестановок, где обменяны 2 соседних элемента, поиском в ширину…»
Дальнейшие слова, думаю, излишни
Задача F. Часы для Офелии
Главное в задаче – понять, что хоть часы и электронные, но повадки механических сохранили (все-таки средние века ). То есть при переводе минутной стрелки вперед с 59 на 00, часовая стрелка перейдет на 1 час вперед. Аналогично при переводе назад. Далее все элементарно – либо рассмотреть возможные случаи, либо сделать поиск в ширину.
Задача H. Быть или не быть?
Достаточно как-нибудь заполнить левый верхний квадрат K x K, а дальше надо его «раскопировать».
