Манхэттенская метрика вроде определяется как сумма модулей разностей координат, а не максимум.
2 2010-10-19 16:57:46
Тема: Расширенный алгоритм Евклида (0 ответов, оставленных в Feedback)
В статье сказано, что алгоритм корректно работает на отрицательных числах.
При A = -5, B = 4 выдает G = -1, X = 1, Y = 1.
Мне кажется, что правильным ответом будет G = 1, X = 3, Y = 4.
3 2010-10-19 16:50:55
Тема: Ошибки в статье "Линейные диофантовы уравнения с двумя переменными" (3 ответов, оставленных в Feedback)
Раздел "Получение всех решений".
x = y0 + k * b / g;Правильно будет
x = x0 + k * b / g;В разделе "Нахождение количества решений и сами решения в заданном отрезке" код
int a, b, c, g, // коэффициенты диофантова уравнения, и g=gcd(a,b)
x0, y0, // одно из решений диофантова уравнения
x1, x2, // заданный отрезок
mx, my; // искомое решение с наименьшим x >= x1
int cnt = (x1 - x0) / b;
if (x0 + cnt * b < x1)
++cnt;
mx = x0 + cnt * b;
my = y0 - cnt * b;следует заменить на:
int a, b, c, g, // коэффициенты диофантова уравнения, и g=gcd(a,b)
x0, y0, // одно из решений диофантова уравнения
x1, x2, // заданный отрезок
mx, my; // искомое решение с наименьшим x >= x1
int cnt = (x1 - x0) * g / b;
if (x0 + cnt * b / g < x1)
++cnt;
mx = x0 + cnt * b / g;
my = y0 - cnt * a / g;4 2009-09-11 19:48:44
Re: Суффиксный массив (2 ответов, оставленных в Feedback)
Если в одной "корзине" лежит несколько одинаковых подстрок, то lcp для всех, кроме одной, равняется длине этих подстрок, а lcp оставшейся равен наибольшему общему префиксу от подстрок этой и следующей "корзины".
Когда на очередном этапе мы видим, что первые половинки новых подстрок на предыдущем этапе были в разных "корзинах", то lcp этих подстрок берем равным тому, что был на предыдущем шаге. Т.е. надо брать "старый" lcp между "корзинами".
В приведенной же реализации (http://e-maxx.ru/algo/suffix_array) берется "старый" lcp от одной из строк первой "корзины", но (как показано в первом абзаце) только для "последней" строки "корзины" мы получим верный ответ. Для всех остальных мы получаем длину всей строки. Проблема в том, что "последней" строки на данном этапе уже может не быть, вернее она перестанет быть "последней".
5 2009-09-10 21:26:09
Тема: Суффиксный массив (2 ответов, оставленных в Feedback)
В разделе "Применение суффиксного массива. Наибольший общий префикс двух соседних суффиксов" есть предложение: "Первые половинки подстрок различались. Заметим, что тогда на предыдущем шаге эти первые половинки необходимо были соседними." Это не так. Если на предыдущем шаге было несколько одинаковых подстрок, то первые половинки могли и не быть соседними.
Пусть дана строка ABAB.
Тогда после первой фазы получим 4 подстроки из 2х символов:
AB
AB
BA
BA
На следующем шаге возможно сравнение первой и третьей (или первой и четвертой) подстрок, хотя они и не являются соседними.
6 2009-08-18 21:30:17
Тема: NEERC 2008 (1 ответов, оставленных в OlympNews)
Кто-нибудь знаешь, где можно достать тесты к задачам последних четверть- и полуфинала. На neerc.ifmo.ru не нашел.
8 2009-07-20 22:15:55
Тема: Абсолютный центр графа. (2 ответов, оставленных в Algo)
Объясните, пожалуйста, что такое абсолютный центр графа (невзвешенного) и как его найти.