Настройки поиска (Страница 12 из 15)

Ох, давно это было...

Мы тогда тоже не смогли придумать нормального решения, двигаться от корня тоже не проходило.

Тогда мы и придумали в итоге это шаманство: мы чем-то там пренебрегли, в итоге получили квадратное уравнение относительно m, решаем его, а потом решение нашей задачи ищем вокруг этих корней.

К сожалению, что за квадратное уравнение такое, я не помню, но понятно уже, что это шаманство полное

То, что ту задачу никто не решил на контесте - можно сказать, недоразумение. Обе команды застряли на других задачах (в том числе даже, возможно, более сложных задачах, чем эта).

Алгоритм: мы перебираем удаляемую вершину. Удаляем эту вершину из графа. Теперь в нём надо найти глобальный мин. разрез (т.е. минимальный среди минимальных разрезов по всем возможным истокам и стокам). Можно перебрать исток и сток, и уже запускать поток (кстати, лучше даже не за куб, а Форда-Факлерсона, почему - скажу ниже). Вот, но это долго - весь алгоритм получается за N^3 * время_потока.

Но заметим, что все пары истоков и стоков перебирать не обязательно, а достаточно зафиксировать произвольный исток, и перебирать только сток. Действительно, зафиксируем любой исток s. В оптимальном ответе (мин. разрезе) он будет находиться в одной доле, а тогда, чтобы найти этот мин. разрез, нам достаточно "угадать" с выбором t так, чтобы он попал в другую долю. Таким образом, для нахождения глобального мин. разреза достаточно зафиксировать, скажем, s=1, и перебирать t=2..n. В итоге получается N^2 * время_потока.

На первый взгляд, это кажется много. Действительно, берём какой-нибудь достаточно хитроумный поток за куб (проталкиванием), и алгоритм получается с асимптотикой N^5. Вот, но утверждается, что как ни странно, можно вместо хитрого потока брать обычного Форда-Фалкерсона. Например, из соображений, что величина потока не может быть большой. И то это будет сильная оценка сверху. Опять же, граф не совсем плотный, и сделать тест, на котором Форд-Фалкерсон будет выполнять много итераций при всех возможных deleted_vertex и t, невозможно. В итоге моё решение за 300 мс работает.

Да, и собственно по мотивам этой задачи я сел разбираться с алгоритмом Штор-Вагнера для нахождения глобального мин. разреза за O(N^3). Решение, основанное на этом алгоритме, имеет общую асимптотику O(N^4), и проходит за 0.

Регистрация открыта (до 3 сентября). Расписание тоже выложили:
Date    Time (UTC)*    Description
August 10     16:00 UTC    Registration Begins (4 weeks)
September 2     23:00 UTC    Qualification Round Begins (24 hours)
September 3     23:00 UTC    Qualification Round and Registration End
September 12     01:00 UTC    Online Round 1 - Sub-round A (2 hours and 30 minutes); Top scoring 1000 contestants advance to Round 2
September 12     16:00 UTC    Online Round 1 - Sub-round B (2 hours and 30 minutes); Top scoring 1000 contestants advance to Round 2
September 13     09:00 UTC    Online Round 1 - Sub-round C (2 hours and 30 minutes); Top scoring 1000 contestants advance to Round 2
September 26     16:00 UTC    Online Round 2 (2 hours and 30 minutes); Top scoring 500 contestants advance to Round 3
October 10     16:00 UTC    Online Round 3 (2 hours and 30 minutes); 25 advance to the Final Round
November 13     TBD    Onsite Finals; 25 Finalists, 1 Champion

По решению Михаила Мирзаянова, на сайте acm.sgu.ru/*** в течение некоторого времени будет открыто дорешивание контестов с этих сборов, но сайт этот будет доступен только для участников сборов.

С архивом контестов (условия, тесты, чекеры) всё несколько проще: он будет распространяться при условии неиспользования этих материалов на публичных контестах, т.е. только для личного пользования.

Причина всего этого - copyrights на задачи, - значительная часть задач была взята из контестов/проблемсетов, поэтому активное распространение этого архива, и уж тем более применение отличное от персонального, крайне не приветствуются.

GeorgeeChebanov, по-видимому надо просто во внутреннем цикле условие "j<k" исправить на "j<k && t<=p[i ]".

Пансионат "Домостроитель"
Сотовая связь, думаю, есть - недалеко же до города.
вид с гугл спутника

Добавлена подсветка кода во все статьи в формате TeX. Использован движок GeSHi.

Ггг, я тоже благополучно пропустил его в том году, так что особо подробностей не расскажу
Ну вообще регистрироваться вроде надо на этом сайте, и пока регистрация не открыта

Добавлено 3 алгоритма:
Дерево Штерна-Броко. Ряд Фарея
Рандомизированная куча
Теория Шпрага-Гранди. Ним

denton
Да, чет официальный перевод кривоватый. Попробую разобраться