Упс. Конечно описался
77 2009-10-13 14:39:04
Re: Динамика по профилю. Задача "паркет" (13 ответов, оставленных в Algo)
Например можно почитать тут http://forums.topcoder.com/?module=Mess … ID=1111225
78 2009-10-13 11:55:11
Re: timus 1144 (1 ответов, оставленных в Problems)
Ты разобрался что нам не нужен наилучший, а нужен любой <= K ?
У меня получилось сдать с таким алгоритмом:
Фаза 1. Жадно разбрасываем по кучам предварительно отсортировав по убыванию
Фаза 2. Начинам оптимизировать пока не добьемся <= K:
Берем наменьшую и каждую другую и стараемся сравнять
Берем наибольшую и каждую другую и стараемся сравнять
79 2009-10-12 22:28:35
Re: Google Code Jam 2009 (12 ответов, оставленных в OlympNews)
winger, emaxx поздравляю с прохождением в финал!
80 2009-10-04 21:56:55
Re: Динамика по профилю. Задача "паркет" (13 ответов, оставленных в Algo)
Кстати доминошную динамику можно реализовать и за O(M*N*M^2)
81 2009-10-01 14:34:22
Re: problem from UVa (2 ответов, оставленных в Problems)
На Codejam Round 2 дали почти эту же задачу...
82 2009-09-23 16:15:41
Re: Статья Нахождение K-го кратчайшего пути (5 ответов, оставленных в Algo)
Максим, именно так я и пытался испрвать - на каждом шаге запускал простой dfs что б проверить найдем ли мы t или нет. Но получилось ужасно медленно .
Пришлось реализовывать Йена который уложился в лимит.
Да и curpath совсем не обязательно строил лексиграфически K-тый маршрут...
Егор, там в начале сказано что самый известный - это Йена. Но это не он.
83 2009-09-22 20:02:47
Re: Статья Нахождение K-го кратчайшего пути (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 2009-09-22 16:03:50
Тема: Статья Нахождение K-го кратчайшего пути (5 ответов, оставленных в Algo)
Привет, Максим
Я тут пробовал решить задачу с помощью http://e-maxx.ru/algo/kth_shortest_path
Идея хорошая, но полностью нерабочая
Не правильно оценена асимптотика - для крайних случаев не O(N^2 * K) а O(N! * K)
на полном графе с 30 вершинам считать будет годами.