Поиск цикла минимального веса
Так как этого алгоритма не было в E-maxx, а он нужен был, пришлось спрашивать об этом на codeforces. Собрать все ответы и сохранить у себя нужно обязательно, поэтому и запишу здесь.
В орграфе:
Можно решить за куб алгоритмом Флоида. Для этого просто проставим все ребра в матрицу смежности, а в остальных местах бесконечность. Запустим Флоида и посмотрим все минимальные пути v~>v. Все эти пути означают минимальный цикл, который содержит данную вершину.
Можно сделать и по-другому. На главной диагонале поставим нули. Все свободные остальные места в матрице приравняем бесконечности. Запустим Флоида. Теперь, чтобы узнать длину минимального цикла, проходящего через ребро v->u, надо взять сумму веса ребра и минимального пути u~>v.
Теперь для не орграфа:
Можно делать так: убираем какое-нибудь ребро v->u и Дийкстрой ищем минимальный путь между u и v, но это работает за O(E*V^2), сделаем по-другому за куб. От каждой вершины v запустим алгоритм Дийкстры. Будем брать каждое ребро, которое не вошло в дерево кратчайших путей u1->u2 и цикл будет v~>u1 + u1->u2 + v~>u2. Для ленивых: дерево кратчайших путей можно составить по отметкам from, которые обозначают из какой вершины проложен кратчайший путь в какую-либо вершину.
С кодом проблем быть не должно.
Границы в неявном дереве отрезков
Сегодня увидел результаты Usaco Feb. contest, и удивился, как по очень легкой задаче я получил очень мало балов. Вспомнив условие и посмотрев свое решение долго не мог понять, как решение получало RuntimeError по Segentation Fault.
Задача была не очень сложной и требавало сканирующую прямую с какой-нибудь структурой данных. У меня это было неявное дерево отрезков. Позже я нашел баг в процедуре обновления на отрезке:
const int BOUND = 100000000;
void upd(int l, int r, int d, int v = 1, int tl = -BOUND, int tr = BOUND) {
if (tl != tr) {
...
}
if (l == tl && r == tr) {
...
} else {
...
}
}
Так как координаты в дереве могли быть отрицательными, дерево охватывало как положительные, так и отрицательные вершины. Тут-то и был прокол. Не во всех случаях это работает, когда мы берем центр отрезка как (tl+tr)/2. Стоило изменить дерево на только положительные вершины, как все тесты стали проходиться.
const int BOUND = 100000000; void upd(int l, int r, int d, int v = 1, int tl = 0, int tr = 2*BOUND)
Вызов функции upd тоже поменял с поправкой на положительность.
USACO.CowXor == IZHO(8).xor
Прорешивал USACO Trainings и увидел задачу с знакомыми условиями и ограничениями. Задача “CowXor” почти равна задаче “xor” с последней Жаутыковской олимпиады. Единственное, что добавили – ответ должен быть больше определенного значения, но решения это почти не меняет.
Даже жаль, реши я эту задачу раньше, а именно до Жаутыковской, мог бы взять больше балов. Хоть это и не изменило ни моей медали, ни абсолютного места, это могло повлиять на места других. А задача была придумана аж в 2005 году. Как жаль, что я до нее дошел только сейчас. Это последняя задача в USACO Trainings.
AntiQuickSort может сломать std::sort
Решаю простую задачу на USACO Trainings наткнулся на проблему. Не проходил 7 тест, выдавал “Segmentation fault”.
В решении нужно было отсортировать 10^4 объектов по своему оператору. Вроде бы, ничего сверхъестественного, но std::sort выпадал в StackOverFlow. Хотя все мне говорили, что в std::sort есть условие, что если слишком глубоко зашли в рекурсию, запустить HeapSort, на g++ решение продолжало падать. После замены на std::stable_sort все заработала, а там, как известно реализована MergeSort.
Надо быть осторожнее.
Бан на Codeforces
Вот я и допрыгался. Решил сегодня поднять один аккаунт. Весь контест отправлял решения за оба логина.
Результат поразителен: я поднял оба аккаунта. Свой поднял до оранжевого цвета. Но в результате бана все вернулось обратно. Печально.
Теперь новая тактика: создать новый аккаунт. Не участвовать в дискуссиях на форуме, а только решать задачи, да побольше.
Думаю, это будет мне уроком. Читерство редко заканчивается хорошо. Пора уже сделать блог закрытым и анонимно участвовать везде, где можно.
Третья Евразийская Олимпиада(UPD)
В этом году от нашего лицея было две команды, старшая состояла из трех учеников одиннадцатого класса, меня с Султаном и Ануаром. Во второй были ученики девятого, десятого и одиннадцатого классов: Стас, Тамирлан и Ислам соответственно.
Третья Евразийская Олимпиада 2011
Завтра уже выезжаем в Алмату. Как и всегда, жить в лицее. Надеюсь на лучшее, да пожалеют меня мои противники и друзья!
Осенний камп в Караганде
Подошел к концу наш камп из четырех дней.
Это даже кампом назвать тяжело. За эти дни мало кто занимался программированием, одиннадцатые классы ходили на подготовку к ЕНТ.
Седьмые классы поражают своей тугодумностью, по маленькому контесту из четырех легких задач с acmp, никто не сдал ни одну. Хоть Ануар и объяснял все так подробно, как мог.
Я же немного объяснял восьмым, поставил тот самый контест для седьмых, а сам лениво решал онлайн системы. Не самый интересный и продуктивный период.
Что самое страшное – осталась одна неделя до Евразийской олимпиады, а моя команда так нормально и не готовилась.
