Итоги поиска единомышленников

Последняя разминка о количестве инверсий в массиве торжественно объявляется самой плодотворной.

Первым представил свое решение Владимир Львович, решив задачу на руби с использованием дерева Фенвика. И не просто решил, а еще и обобщил задачу до решения с целыми и действительными числами. В итоге Львович предоставил нам три реализации своего алгоритма.

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

Последнее по счету, но никак не последнее по важности идет, вдохновленное скринкастом Дмитрия, решение Антон Ильина с текстовым отчетом о проделанной работе у себя в блоге. Статья обязательна к прочтению всем интерисующимся. Антон рассказывает нам об этой новой структуре данных - дерева Фенвика. Новую с точки зрения открытия - Питер Фенвик придумал эту структуру в 1994 году, что, согласитесь, совершенно недавно.

В итоге сложность решения задачи была сведена к O(N*log(N)) во всех решениях.

raven29-int.rb    0.762s
raven29-real.rb   1.213s
bronislav.rb      0.688s
donal.rb          1.106s