Блог пользователя permin

Автор permin, 9 лет назад, По-русски

Всем привет!

Внезапно оказалось, что SnarkNews winter series — 2015 уже идет! Я вот чуть в очередной раз не пропустил серию.

UPD2: Первый раунд закончен, можно обсуждать задачи :)

UPD4, UPD: Второй раунд закончен, можно обсуждать задачи.

UPD3, UPD6: Третий раунд уже закончен.

UPD5, UPD7: Четвертый раунд закончился.

UPD8, UPD9: Пятый раунд уже закончился.

Спасибо snarknews за организацию соревнования.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +59
  • Проголосовать: не нравится

Автор permin, 10 лет назад, По-русски

Через два часа (16:00 MSK) состоится Single Round Match 611. Не пропустите, и желаю удачи!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор permin, 13 лет назад, По-русски
О задаче потоке с ограничениями рассказано http://e-maxx.ru/algo/flow_with_limits, там же написан алгоритм решения задачи. И я всегда(после того, как прочитал) думал, что все хорошо. Давно сдал задачку на sgu 176. Flow Construction. А вот сейчас рассмотрел такой пример, и в нем происходит не то, что должно.
Вначале в общих словах. Пусть в графе все ребра (ориентированные) имеют верхнюю границу потока 1, а нижнюю -- все 0, кроме одного (с нижней границей 1). Тогда если в этом графе есть цикл, проходящий через это самое ребро(но не содержащий истока-стока), то алгоритм скажет, что это ребро можно насытить, хотя насытить его можно не всегда.  Действительно из нового истока S' будет идти одно ребро, в конец этого ребра, а в T' тоже одно, но из начала. Тогда будет существовать путь из S' в T' (то есть поток не нулевой, то есть не меньше, чем сумма все нижних границ, которая равна 1, значит ребро можно насытить).  Почему существует путь из S' в T': выделенное ребро(с нижней границей = 1), участвует в цикле, то есть из конца этого ребра, можно попасть в начало этого ребра. (S' -> конец ребра -> начало ребра -> T'). 

Конкретный пример:
Граф задан в формате задачи http://acm.sgu.ru/problem.php?contest=0&problem=176
7 7
1 6 1 0
6 2 1 0
2 3 1 1
3 4 1 0
4 5 1 0
5 2 1 0
6 7 1 0

и моя программа, получившая accepted, выдает:
0
0 0 1 1 1 1 0
Хотя насытить ребро 2-3 нельзя. 

Получается, ошибка или в алгоритме, или в моих рассуждениях. Буду рад помощи. 

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор permin, 13 лет назад, По-русски
21 октября в 15:02 MSD состоялся очередной TopCoder SRM. Предлагаю здесь вести обсуждение. 

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится