Всем привет!

Вот здесь в заметках от PavelKunyavskiy наткнулся на следующее утверждение:

Говорят, крутая оптимизация Форда-Беллмана: поддерживать лес меток и при релаксации вершины удалять её поддерево из очереди (или просто обновить расстояние до них всех). "Даёт ускорение в десятки раз", надеюсь, не потребуется.

А может кто-нибудь рассказать про это подробнее? :)

Привет, народ!

Пара фоток со сборов в МФТИ + экскурсия в Яндекс! :)

Привет, народ!

Вот ещё пара фоток со сборов в Сазанке! :)

Всем привет!

Наконец, дошли руки выложить пару фоток с Чемпионата Урала 2014... :)

Добрый день!

На главной странице SnarkNews написано, что "XIV Открытый Кубок им. Е.В. Панкратьева по программированию стартует 29.09.2013", а в официальном расписании дата первого контеста назначена на 06.10.2013.

Так будет ли в это воскресенье OpenCup? Если да, то во сколько? Если нет, то когда будет? :)

UPD: 06.10.2013

Всем привет! Уже прошла целая вечность с момента окончания зимних сборов в Ижевске :)

Здесь можно посмотреть некоторые фотки, которые я там сделал :)

Остальные фотки (чуть меньше тысячи) можно посмотреть в альбоме на Picasa. Приятного просмотра! :)

Всем привет!

Недавно закончились сборы программистов в Ижевске. Здесь можно посмотреть некоторые фотки, которые я там сделал.

В ожидании контеста...

Авторский разбор Паши Хаустова

Еду получить не так-то просто :)

Послушали легенду о Лопшо Педуне :)

Мастер-класс по приготовлению перепечей

Удмуртская народная игра с пеньком :)

Almaty IITU #1 (Kovalenko, Bolshakov, Kutybaev)

Ural FU #1 (Krasnoselskikh, Nazarov, Mukhametyanov)

Ufa SATU (Lezhankin, Ripatti, Mazgarov)

Остальные фотки можно посмотреть в альбоме на Picasa. Приятного просмотра! :)

Здравствуйте!

Не так давно закончился пятый тур SnarkNews winter series — 2012. Поэтому, наверное, уже можно обсуждать задачи? У многих участников задача D — Triangles and circles не зашла с первого раза.

Мне бы очень хотелось узнать, как её решали другие участники. Если где-нибудь уже есть разбор этой задачи, прошу прощения, не нашел. Буду очень благодарен, если кто-то поделится ссылкой на него или напишет, как делал.

К сожалению, я пока так и не смог преодолеть в дорешке барьер WA 5 :)

Решить её пытался следующим образом:

Проверка условия

можно ли треугольник со сторонами a, b, c поместить внутрь окружности радиуса r так, чтобы все его точки лежали внутри или на границе окружности.

1. Если треугольник остроугольный

Т.е., если выполняется условие:

В этом случае треугольник можно поместить внутрь окружности, если радиус описанной окружности будет не больше радиуса заданной окружности:

Площадь S найдем по формуле Герона:

где

Подставив, получим исходное неравенство в следующем виде:

что равносильно

2. если треугольник не остроугольный

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

Определение максимального числа возможных пар

Я делал следующим образом:

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

1. Составим списки смежности вершин одного типа с другими.
2. Среди вершин одного типа находим вершину с наименьшей степенью.
3. Затем перебираем смежные с ней вершины и находим там с наименьшей степенью.
4. Удаляем ребро, которое соединяет эти вершины вместе с самими вершинами. Следовательно, удаляются ребра, которые исходили из этих вершин. И увеличиваем ответ на 1.
5. Повторяем шаги 2 — 4 пока остаются ребра.

Заключение

Скажите, пожалуйста, где и что я делаю не так. Вот мой горекод, который падает с WA 5.

Спасибо!