Рубрика «Спортивное программирование» - 29

Алгоритм поиска наименьшего общего предка в дереве

2013-10-21 в 16:34, admin, рубрики: алгоритм, Алгоритмы, Спортивное программирование, метки: алгоритм, спортивное программирование

На досуге мне пришла интересная идея, которую я развил в алгоритм нахождения наименьшего общего предка(LCA) двух вершин в дереве. До появления этой идеи других алгоритмов для поиска LCA я не знал. Проверив корректность работы я поспешил изучить другие алгоритмы для решения этой задачи, но аналогичных моему я не нашел. Теперь поспешу поделиться им с сообществом.

Введение

Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.
Наименьшим общим предком двух вершин u и v будет называться такая вершина p, которая лежит на пути из корня и до вершины v, и до вершины u, а также максимально удаленная от него.
Читать полностью »

OSA Rescuer — система построения GPS-маршрутов для эвакуации из зон бедствия [Первый опыт]

2013-10-10 в 5:58, admin, рубрики: android, java, Программирование, робототехника, Спортивное программирование, метки: android, c++, java, робототехника

“OSA Rescuer — автоматизированный комплекс содействия МЧС и построения GPS-маршрутов для эвакуации из зон бедствия”.Читать полностью »

11-13 октября в Ростове-на-Дону пройдет марафон разработки IT-проектов «47 hours»

2013-10-09 в 15:45, admin, рубрики: microsoft, анонс, конференция, Программирование, разработка, Спортивное программирование, хакатон, метки: microsoft, анонс, конференция, мастер класс, Хакатон

11-13 октября в Ростове-на-Дону пройдет марафон разработки IT-проектов «47 hours» + конференция и мастер-класс от Microsoft

Вновь на одной площадке соберутся активные представители южного IT-сообщества: разработчики, тимлиды, менеджеры проектов, дизайнеры, иллюстраторы, копирайтеры, специалисты по маркетингу и предприниматели.
Читать полностью »

Финал чемпионата по программированию Russian Code Cup: как это было

2013-10-07 в 10:18, admin, рубрики: mail.ru, rcc, Russian Code Cup, Блог компании Mail.Ru Group, олимпиадное программирование, Программирование, Спортивное программирование, метки: mail.ru, rcc, Russian Code Cup, олимпиадное программирование

Продолжаем традицию подробных отчетов о финалах RCC (прошлогодний аналогичный пост — здесь). Итак, 23 сентября 2013 года завершился третий чемпионат по спортивному программированию — Russian Code Cup 2013. Первое место занял Петр Митричев, повторив собственное достижение 2011 года, второе — Геннадий Короткевич, победивший в этом году вместе с командой ИТМО в финале ACM ICPC в Санкт-Петербурге. Третьим стал Дмитрий Джулгаков, уже третий раз участвовавший в финале чемпионата, но впервые завоевавший призовое место.

Финал чемпионата по программированию Russian Code Cup: как это было Читать полностью »

ClojureCup 2013 — отчет команды («unmatched

2013-10-02 в 11:48, admin, рубрики: clojure, clojurecup, clojurescript, ненормальное программирование, Спортивное программирование, хакатон, метки: clojure, clojurecup, clojurescript, Хакатон

В минувшие выходные Clojure-сообщество испытывало огромные волнения в силе. За 48 часов требовалось ни много ни мало написать любое веб-приложение. Команды вплоть до 4-х человек, весь код (помимо библиотек, конечно), дизайн и ассеты должны создаваться с нуля в течение соревнования.

Страница соревнования: http://clojurecup.com/
Читать полностью »

RuSSIR Music Hackathon 2013: как это было

2013-10-02 в 6:52, admin, рубрики: russir, Zvooq, Веб-разработка, Работа со звуком, Спортивное программирование, хакатон, метки: russir, Zvooq, Хакатон

В ночь с 20 на 21 сентября в рамках VII школы-конференции по информационному поиску RuSSIR 2013 в Казани состоялся первый российский музыкальный хакатон RuSSIR Music Hackathon. На правах главного организатора, я хотел бы представить рассказ об этом событии. Данный пост посвящен тем впечатлениям, которые мог получить очевидец события, а следующий пост будет содержать более эксклюзивную информацию — заметки организатора.

Наше мероприятие проходило при поддержке Казанского федерального университета, Высшей школы ИТИС КФУ, НП РОМИП, а главным спонсором и партнером выступил Zvooq — музыкальный сервис компании Dream Industries.

Итак, лейтмотивом нашего хакатона стало создание приложений в области музыки в режиме 24 часов. Участники не были ограничены ни типом приложений, ни платформой для реализации. Благодаря тому, что мероприятие проводилось в те же дни, что и школа RuSSIR, наш хакатон собрал довольно уникальный состав участников (всего — 34 человека): в основном, это были молодые ученые из разных городов Европы и России, а также казанские профессионалы-разработчики. По этой причине английский язык стал основным языком общения во время мероприятия. Кроме того, сама площадка для проведения — аудитории университета — придавала особую атмосферу: вместо ночи музеев — ночь в университете!

Читать полностью »

4-6 октября в Киеве пройдет мировой хакатон #hack4good!

2013-10-01 в 9:43, admin, рубрики: hack4good, киев, Презентации, Спортивное программирование, хакатон, метки: hack4good, киев, Хакатон

geeklist

#hack4good это уникальный мировой хакатон, который фокусируется на объединении самых крутых программистов, дизайнеров, девелоперов и предпринимателей. Вместе мы делаем мир лучше, создавая проекты, которые помогают человечеству. Следующий хакатон пройдет 4-6 октября во многих городах мира, и в Киеве в том числе!

Участники #hack4good создают решения, которые помогают как человечеству в целом, так и окружающей среде, цель хакатона – предложить решение для глобальных проблем.

Мировые организаторы приготовили для самых воодушевленных команд призы:Читать полностью »

Новая олимпиада по новому языку: открываем регистрацию!

2013-10-01 в 7:31, admin, рубрики: acm, java, kotlin, апрель, Блог компании JetBrains, олимпиада, Спортивное программирование, метки: acm, kotlin, апрель, олимпиада

Компания JetBrains открывает регистрацию на Kotlin Challenge — соревнование по программированию для тех, кто хочет попробовать новый язык программирования для платформы Java.

Помните, на конференциях вы слышали доклады по Kotlin? Помните, кто-то из друзей вдохновенно рассказывал о том, что вот-вот появится новая Java от JetBrains? Помните, младшая сестра жаловалась, что никак не освоит Kotlin, потому что нет русской документации? Теперь все изменилось: мы начинаем свою собственную олимпиаду по Kotlin, и даже сделали немного документации по-русски для тех родных заядлых олимпиадников, которые еще не изучили даже технический английский.

Мы приглашаем к участию в Kotlin Challenge всех, кто любит сложные олимпиадные задачи и всех, кто пробует самое свежее в информационных технологиях, чтобы сыграть роль первопроходцев, покоряющих неизведанный край нового языка, сразиться с серьезными соперниками и выиграть почет, славу и призы.

Важно:
Читать полностью »

Мобильные приложения на службе у городских властей

2013-09-30 в 9:00, admin, рубрики: open data, мобильные приложения, Спортивное программирование, электронное правительство, метки: open data, мобильные приложения

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

В начале хотел бы упомянуть об инициативе Open Government Data, суть которой заключается в том, чтобы правительства и локальные советы выкладывали свои данные в открытом доступе, чтоб их мог использовать любой желающий. Это необходимо для обеспечения прозрачности деятельности правительств и значительным образом увеличивает информированность граждан. На сайте datacatalogs.org можно найти список каталогов открытых данных по всему миру. По запросу Russia выдается пять результатов:

budget.gov.ru. Russia open budget / open spending portal
data.mos.ru. Moscow city administration open data portal, Russia.
data.openpolice.ru. Data portal for Open Police project, Russia
OpenGovData Russia. Catalog OpenGovData.ru is a public data catalog published by the Russian Government
DataGov.ru. CKAN community site, Russia

А вот по запросу Ukraine, к сожалению, 0 :(
Читать полностью »

Задачка из реальной жизни: Как восстановить дерево процессов в Linux

2013-09-26 в 9:57, admin, рубрики: algorithms, CRIU, linux, system programming, Алгоритмы, олимпиадное программирование, олимпиадные задачи, системное программирование, Спортивное программирование, метки: algorithms, CRIU, linux, system programming, олимпиадное программирование, олимпиадные задачи

Мы разрабатываем проект CRIU (Checkpoint/Restore in Userspace) и у нас возникла достаточно интересная задача о том, как восстановить оригинальное дерево процессов. Я предлагаю вам попытаться решить ее.

Задача

CRIU — это утилита, которая позволяет сохранить состояние процессов на диск и постановить их позднее на этой или на любой другой машине. Одной из подзадач восстановления является нахождение последовательности действий для того, чтобы восстановить дерево процессов. Входные данные содержат набор параметров для каждого процесса: уникальный идентификатор (PID), ссылку на родителя (PPID), идентификатор сессии (SID).