1

Тема: Feedback

Спасибо за проделаную роботу! Прочитал практически все алгоритмы :-) И нашел несколько ошибок(опечаток):

В функции Эйлера, доказательство мультипликативности:
    если x взаимнопросто с a, то не следует, что x mod a = 1 (например x=7, a=4 (7 mod 4 = 3) или x=8, a=5 (8 mod 5 = 3))

В алгоритме Штор-Вагнера, Доказательство:

    "наиболее сильно сильно связанную"
    лишнее слово "сильно".

    "то обозначим предпоследнюю добавленную вершину через s, а предпоследнюю — через t."
    Наверное, "последнюю через t".

    "но не ещё не были учтены в"
    лишнее "не"

В алгоритме Куна:
    Увеличивающей цепью ... назовём цепь,
    Наверное, "назовём чередующуюся цепь".

Матрица Татта:
    "Напомним, что паросочетание "
    Нету продолжения(((

    "некоторого полинома относительно переменных-элементов этой матриц"
    Наверное, "матрицы".

Центры тяжести многоугольников и многогранников:
    "Мы считаем, что масса распределена по фигуре однородна"
    Наверное, "распределенная" или "однородно".

Нахождение площади объединения треугольников. Метод вертикальной декомпозиции:
    "найдём все точки пересечения всех отрезков (образующих треугольники), и отсортируем найденные точки"
    Наверное, следует упомянуть о том, что отсортировать надо по X.

Нахождение вписанной окружности в выпуклом многоугольнике методом "сжатия сторон":
    "больше сдвигать стороны мы не сможет"
    Наверное, "сможем".

Z-функция строки и её вычисление:
    Пример 2: aaabaab; z[4] должно быть 2 а не 3.

    "Применения эти будут во многом аналогичным применениям \alohref=prefix_function{префикс-функции}."
    опечатка в ссылке на префикс функцию.

Суффиксный массив. Наибольший общий префикс двух подстрок: способ с дополнительной памятью
    Наверное, не за О(1), а за О(log(N)).

Sqrt-декомпозиция:
    "которая позволяет некоторые типичные операции (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за"
    не хватает слова "выполнять".

    "Рассмотрим ещё одну интересную вариацию идею"
    Наверное, "вариацию идеи".

Дерево отрезков:
    Усложнённые версии дерева отрезков:
        мы должны просто по двум таким пары
        Наверное, "парам".
    Присвоение на отрезке
        "западывающее" обновление
        запаздывающее

Декартово дерево (treap, дерамида):
    "Merge (T1, T2) ... (все значения в первом меньше значений во втором)"
    Возможно, следует указать "(все значения Y в первом меньше значений Y во втором)"

Задача Иосифа
    "чем рассмотренная выше динамика" - на самом деле, динамики выше нет.

И несколько пожеланий/предложений:

В алгоритме Диница:
обязательно ли запускать несколько dfs'ов? Такой вариант вроде б должен быстрее работать (и коду меньше):
    int dfs (int v, int flow) {
        if (!flow)  return 0;
        if (v == t)  return flow;
        int rest=flow;
        for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
            int id = g[v][ptr[v]],    to = e[id].b;
            if (d[to] != d[v] + 1)  continue;
            int pushed = dfs (to, min (rest, e[id].cap - e[id].flow));
            if (pushed) {
                e[id].flow += pushed;
                e[id^1].flow -= pushed;
                rest-=pushed;
                if (!rest)
                    return flow;
            }
        }
        return flow-rest;
    }
    
    int dinic() {
        int flow = 0;
        while (bfs()) {
            memset (ptr, 0, n * sizeof ptr[0]);
            flow+=dfs(s,INF);
        }
        return flow;
    }
Если нет, то укажите, пожалуйста на ошибку.

Пересечение окружности и прямой:
    возможно, лучше формулы переделать в TeX.

Префикс-функция. Алгоритм Кнута-Морриса-Пратта:
    Сжатие строки - может просто вставить ссылку на соответствующую статью?

Может в книге сделать текст пошире?

2 Отредактировано KADR (2011-09-23 21:32:49)

Re: Feedback

Насчет Диница: нет, это не быстрее. Такой код выходит эквивалентным алгоритму Эдмондса-Карпа, только константа больше. Ведь на каждой итерации бфса поток пропускается только через один путь.

3

Re: Feedback

Ну почему же через 1 путь? В dfs'е все так же пропускается блокирующий поток (не только 1 путь). Посмотри внимательнее - в dfs return flow только если уже нечево пропускать с текущей вершины (в rest поддерживается количество потока, которое еще можно пропустить на следующий уровень). И так же отсекаются "тупики" (через ptr).

4

Re: Feedback

Интересно. Вроде бы такое решение пропускает все что можно дфсом, но тем не менее, на SPOJ получает TL, при том что мой Диниц там за 0.41 проходит (ТЛ 5 секунд).

5

Re: Feedback

Я получил АС на SPOJ этим алгоритмом (3.5 сек). Реализация e-maxx'а получила 3.75 сек. Возможно, у тебя INF был недостаточно большим. (задача FASTFLOW).

P.S. Можеш поделиться своей реализаціией? Я смог из Диница выжать только 3.3 секунды на SPOJ.

6

Re: Feedback

Да, точно, INF поставил маленьким smile

Отправил в приват реализацию.

7

Re: Feedback

Oracle, вы проделали просто фантастическую работу! Огромное спасибо за такой подробный отчёт. Такое ощущение, что вы дотошно прочитали буквально каждую статью smile

Пересечение окружности и прямой:
    возможно, лучше формулы переделать в TeX.

Да уж, эта статья писалась в те тёмные времена, когда я ещё не знал про TeX smile

Префикс-функция. Алгоритм Кнута-Морриса-Пратта:
    Сжатие строки - может просто вставить ссылку на соответствующую статью?

Ну я бы скорее удалил статью "сжатие строки", т.к. она не особо содержательна.

Может в книге сделать текст пошире?

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


KADR, а можно в паблик какие-нибудь подробности по поводу алгоритма Диница? Всё же десятикратное ускорение означает какое-то фундаментальное отличие, хотя моя реализация вроде бы написана в соответствии с теорией.

8

Re: Feedback

Спасибо :-)
Да, в книге текст занимает только около 60-70% ширины страницы.