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

Тест для TLE алгоритма Левита (aka SPFA)
Автор mage, 13 лет назад, По-русски

В решении задачи 144D некоторые участники использовали алгоритм, известный под названием алгоритм Левита (на английском попадается под названием SPFA).


Хочу поделиться тестом, который заваливает все найденные мною сабмиты с той или иной модификацией этого алгоритма.

Тест:
n 2*n-3 1
1 2 1000000000 / 2
1 3 1000000000 / 3
1 4 1000000000 / 4
....
1 n 1000000000 / n
2 3 1
3 4 1
......
n-1 n 1
l

и для случая, когда вершины в списке смежности оказываются в обратном порядке:
n 2*n-3 1
1 n 1000000000 / n
1 n-1 100000000 / n-1
...
1 2 1000000000 / 2
2 3 1
3 4 1
......
n-1 n 1
l

генератор: https://gist.github.com/1652283

сабмиты, которые заваливаются:

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

»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
for(int i = 0; i < n; i++) {
Collections.shuffle(g[i]); // Удачных взломов
}
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Да, крутой тест. Только для больших n часто оказывается, что и серии апдейтов из вершины i не происходит. Поэтому правильнее сделать так:
1 2 n
1 3 n-1
1 4 n-2
...
1 n 2
2 3 0
3 4 0
4 5 0
...
n-1 n 0

Кажется, никакие известные модификации алгоритма от этого теста не спасут. Только если random_shuffle или sort ребер.

В 144D - Ракетные шахты веса ребер были до 1000 - при таких ограничениях у нас не получилось завалить Левита.

→ Ответить