ICFPC 2012. Как мы дерево из массива вырастили!

[xoposhiy]

Итак, после первого раунда мы, hack the loop, 15-ые! Значит все таки надо написать отчёт. Впрочем впереди нас ждет ещё один отборочный тур, в котором отсеют ещё половину участников, а потом финальный тур, результаты которого мы узнаем лишь осенью во время конференции ICFP 2012.

Comments

[anonymous]

Ну не гад, а?
Нет бы указать прямо что за язык программирования использовался и дать ссылку на код - теперь на меня наседают коллеги с требованием заключения пари :)
P. S> капча "0-covectors." доставила - мы все под колпаком у Мюллера :-D

[xoposhiy]

Ссылка на github присутствует в конце. Язык C#. Без капчи для анонимусов мне придет смерть от спама

[ext_870861]

Насколько я знаю, говорят "sqrt-декомпозиция" http://e-maxx.ru/algo/sqrt_decomposition

[ext_365505]

Внезапно даже захотелось самому реализовать. Интересно написал.

Не пробовали хранить построчно и оставлять те строки, которые не поменялись?

[anonymous]

Насколько я понимаю, immutable - это просто неизменяемая, как строки в .Net. Создавая новую строку, мы копируем всё содержимое старой, не создавая каких-либо ссылок на общий для старой и новой строки контент, для того, чтобы хранить его один раз. Поэтому, например, взять подстроку в .Net - это O(N), а не O(1) операция.
Persistent - это именно immutable + "храним общие части между старым и "преобразованным" значением один раз и делаем на них ссылки". В книжке Окасаки про это классно написано. Видимо, от её названия и идёт Purely Functional, но что из вышеперечисленного под этим подразумевается - понятия не имею :)

[xoposhiy]

Не знаю, не знаю. В Java string тоже называют immutable, но там общий буффер и substring за O(1).

[an_ger]

А вот и финальные результаты: http://www-fp.cs.st-andrews.ac.uk/~icfppc/scoretable-final.txt