Подскажите, пожалуйста, задачу на каком-нибудь из online judges, которая решается с помощью симплекс-метода. Недавно проходили его в университете и хочется проверить, правильно ли я пишу этот алгоритм.
На самом деле не надо там ничего оптимизировать. С теми ограничениями абсолютно любая вменаемая реализация проходит на ура. В разные времена "Триатлон" служит тестовой площадкой для разных по степени криворукости моих реализаций симплекс-метода :) И они все проходили за 0.016, если мне не изменяет память.
Что касается получаемых командами ТЛ-ей - на тестах этой задачки случается достаточно редкое явление - зацикливание СМ. В этом и есть причина. Один из способов борьбы - "Правило Бленда" (вроде так), описано в Кормене или гугл. Состоит в дописании примерно одной строчки к коду СМ...
Очень многие классические задачи на графах можно сформулировать в терминах ЛП. В принципе, подойдут даже задачки на "Дейкстру" и т.д. :) Преимущество потоков состоит в том, что метод Форда-Фалкерсона является чем-то вроде прообраза симплекс-метода, сформулированного на графах. Есть подозрения, что реальное время работы будет достаточно близко. Если кто-то сравнивал поток через ФФ и СМ на одних тестах - интересно было бы послушать...
Затем по такому же принципу a[i][j] = a[i - 1][j + 1] - a[i - 1][j] для 1 ≤ i ≤ k, 0 ≤ j ≤ k - i. То есть получаем треугольник из попарных разностей значений предыдущей строчки.
Далее возьмём первый столбец (c0 = a[0][0], c1 = a[1][0], ..., ck = a[k][0]).
Но там надо чуть соптимизировать. Подробности есть в обсуждении задачи.
На самом деле не надо там ничего оптимизировать. С теми ограничениями абсолютно любая вменаемая реализация проходит на ура. В разные времена "Триатлон" служит тестовой площадкой для разных по степени криворукости моих реализаций симплекс-метода :) И они все проходили за 0.016, если мне не изменяет память.
Что касается получаемых командами ТЛ-ей - на тестах этой задачки случается достаточно редкое явление - зацикливание СМ. В этом и есть причина. Один из способов борьбы - "Правило Бленда" (вроде так), описано в Кормене или гугл. Состоит в дописании примерно одной строчки к коду СМ...
http://www.codechef.com/problems/OVENTIME
Для тестирования, думаю, любая задача на поток подойдет.
Вроде как в чистом виде на Тимусе
На самом деле если посмотреть на матрицу в этой задаче можно предложить итеративное решение. Без Гаусса.
А вот вроде в этой этой задаче как раз надо решить СЛУ.
Первый способ.
Второй способ не такой универсальный, как первый, но в принципе очень удобный.
Как раз при нахождении формулы для какой-то последовательности, которая задаётся каким-то многочленом.
Пусть у нас есть значения многочлена в точках {0, 1, 2, ..., k} — P(0), P(1), ..., P(k).
Тогда обозначим a[0][0] = P(0), a[0][1] = P(1), ..., a[0][k] = P(k).
После этого вычислим a[1][0] = a[0][1] - a[0][0], a[1][1] = a[0][2] - a[0][1], ..., a[1][k - 1] = a[0][k] - a[0][k - 1].
Затем по такому же принципу a[i][j] = a[i - 1][j + 1] - a[i - 1][j] для 1 ≤ i ≤ k, 0 ≤ j ≤ k - i. То есть получаем треугольник из попарных разностей значений предыдущей строчки.
Далее возьмём первый столбец (c0 = a[0][0], c1 = a[1][0], ..., ck = a[k][0]).
Искомый многочлен имеет вид