Marathon 68 -- BeautifulCrossword
Идея поучаствовать в четырехнедельном марафоне заманчива, но для этого, во-первых, нужны четыре недели, а во-вторых, в первом раунде не будет 50-ти лучших марафонцев, и в чем тогда смысл. Короче, чтобы пропустить первый раунд TCO, решил принять участие в последнем марафоне, который давал возможность обновить свой рейтинг и выполнить условие активности за последние шесть месяцев. Результат: обновил и выполнил. Уроки на будущее: тщательно проверять дату окончания марафона; даже если марафон проходной, не оставлять все на последний день. Состояние, когда видишь пустую страницу там, где должна была быть ссылка Submit, словами, наверное, передать можно, но нужен талант. 36-место, -82, желтые штаны.
2011 TCO Round 2 -- QualityPolygons
Отличная задача! Простое и понятное условие (вопросов на форуме практически не было), вся геометрия в целых числах (никаких уплывающих запятых), глубина (это когда новые грабли обнаруживаются только на второй неделе). Идея, стоящая упоминания: поскольку необходимо было часто для произвольной вычисленной точки находить ближайшую из заданного множества, а также всех ее соседей, была реализована дискретная диаграмма Вороного. При инициализации для каждой точки заданного пространства 700х700 методом динамического программирования была вычислена ближайшая исходная точка, и для каждой исходной точки в том же процессе были определены все соседи. Две структуры данных позволяли быстро находить (x,y) -> point -> neighbors[]. Новшество марафона: искусственное выделение двух областей параметров; в первой возможен полный (или близко к тому) перебор, во второй без эвристик делать нечего. Результат: 25-е место, +25.
2011 TCO Round 3 -- StringCompression
Случилось страшное: все четыре области параметров позволяли достигать оптимального (или по-крайней мере очень к нему близкого) результата. Это грозило тем, что за две недели количество претендентов на первое место заметно превысило бы 12, проходящих в финал. Трудно сказать, насколько правильным было решение изменить правила через пять дней после начала марафона, но проблему с парой десятков первых мест TC, конечно, решил. В результате пришлось решать две разные задачи: восстановление зашумленной строки и сжатие практически белого шума. Главный результат для меня - удалось применить алгоритм восстановления с итеративной нормализацией. Теперь, когда есть практический опыт его (алгоритма) применения, будем искать возможности его (опыта) расширения. Предварительный результат. 18-е место с очень малыми шансами на улучшение. Update: 15 место, +41, красные штаны. Всего 1% отделял от 12-го места, было за что бороться.