76

(13 ответов, оставленных в Algo)

Упс. Конечно описался smile

77

(13 ответов, оставленных в Algo)

Например можно почитать тут http://forums.topcoder.com/?module=Mess … ID=1111225

78

(1 ответов, оставленных в Problems)

Ты разобрался что нам не нужен наилучший, а нужен любой <= K ?

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

Фаза 1. Жадно разбрасываем по кучам предварительно отсортировав по убыванию
Фаза 2. Начинам оптимизировать пока не добьемся <= K:
Берем наменьшую и каждую другую и стараемся сравнять
Берем наибольшую и каждую другую и стараемся сравнять

79

(12 ответов, оставленных в OlympNews)

winger, emaxx поздравляю с прохождением в финал!

80

(13 ответов, оставленных в Algo)

Кстати доминошную динамику можно реализовать и за O(M*N*M^2)

81

(2 ответов, оставленных в Problems)

На Codejam Round 2 дали почти эту же задачу...

82

(5 ответов, оставленных в Algo)

Максим, именно так я и пытался испрвать - на каждом шаге запускал простой dfs что б проверить найдем ли мы t или нет. Но получилось ужасно медленно sad.
Пришлось реализовывать Йена который уложился в лимит.

Да и curpath совсем не обязательно строил лексиграфически K-тый маршрут...


Егор,  там в начале сказано что самый известный - это Йена. Но это не он.

83

(5 ответов, оставленных в Algo)

Это не так.

Для K = 200, N = 30, W = 1000 легко подобрать случай  когда решаться будет в O(30!)

"Этот нюанс специально контролируется тем, что мы не идем в те вершины, для которых предпросчитанное Дейкстрой расстояние больше чем надо. " Тоже не верно там чтоит <= то есть мы можем долго и упорно беребирать все возожные пути


Для наглядности - пусть у нас полный граф для 30 вершинами и еще одна 31 вершина которая идет в 1.

Пусть мы теперь запускаем kth_path_exists (100, 100, 1)   и t = 31

Первый же вызов сделает used[1] = true   т.е получится что в 31ю нам никак больше не добраться и алгоритм начнет перебирать все 30! путей пока не убедится что единственный путь это 1-31.

84

(5 ответов, оставленных в Algo)

Привет, Максим

Я тут пробовал решить задачу с помощью http://e-maxx.ru/algo/kth_shortest_path

Идея хорошая, но полностью нерабочая smile
Не правильно оценена асимптотика - для крайних случаев не O(N^2 * K) а O(N! * K)

на полном графе с 30 вершинам считать будет годами.