Sunday, December 2, 2012

NEERC 2012 Results

NEERC 2012 Results (full results at official site: http://neerc.ifmo.ru/information/standings.html). Teams at 2nd and 3rd places got their last problem accepted 3 seconds before the end and 24 seconds before the end, respectively :)

RankTeamABCDEFGHIJKL=Time

1SPb NRU ITMO 1 (Kever, Korotkevich, Nigmatullin)+
14:14
+3
105:18
+1
42:11
+3
238:02
+
30:36
+
205:53
+
9:45
+
19:13
+
183:46
+
78:00
-10+1
146:06
111229
2Moscow SU 1 (Fedorov, Kaluzhin, Rogulenko)+
18:17
+1
80:33
+
142:36
+4
299:57
+
54:18
+
183:44
+
12:10
+
36:50
.+
143:55
.+1
254:43
101341
3Belarusian SU 1 (Malevich, Udavichenka, Zhgirovski)+
16:39
+
170:35
+
116:29
.+3
108:38
+
214:43
+
24:26
+
29:59
+6
299:36
+
182:16
.+
153:35
101491
4SPb SU 4 (Egorov, Kunyavskiy, Suvorov)+
13:02
+
94:29
+
74:20
+4
295:35
+1
45:00
+1
278:39
+
9:04
+1
23:24
+2
253:34
+3
259:24
..101583
5SPb NRU ITMO 4 (Bardashevich, Kucherenko, Vedernikov)+
11:22
+3
180:24
+
110:13
.+
92:41
+
233:45
+2
33:57
+
44:46
.+
164:04
.+
290:50
91257
6Moscow SU 4 (Kumok, Permin, Tikhomirov)+
16:59
+1
76:58
+
176:44
.+
108:56
.+1
41:12
+
47:44
+4
291:35
+
144:07
.+
278:57
91297
7Moscow SU 5 (Artuhin, Ignatev, Paramonov)+1
32:19
+2
159:37
+
127:49
.+
91:53
+
183:37
+
51:06
+
64:24
-2+
207:09
.+5
278:21
91352
8Ural FU 2 (Dolgorukov, Shchelkonogov, Soboleva)+
16:34
+3
221:44
+1
137:18
.+1
281:08
+
85:51
+
43:21
+1
68:16
.+1
172:57
.+
238:00
91401
9Moscow SU 3 (Evstropov, Ivlev, Pyaderkin)+
24:49
+4
194:06
+4
76:55
.+
97:13
+
289:16
+
37:03
+1
61:52
-1+1
196:58
.+1
261:24
91455
10Moscow SU 2 (Dubinin, Mokin, Sadkov)+1
14:12
+1
182:00
+3
146:59
.+3
125:17
+1
246:48
+1
21:42
+5
179:22
.+1
223:09
-1+
287:01
91743

NEERC 2012 - Комментарии

15:16 - Контест закончен. Результаты будут известны сегодня вечером, через 4-5 часов. Я напишу про это отдельный пост, на английском. Трансляция на этом завершена, но если у вас остались вопросы, пишите их в комментарии, постараюсь ответить.

15:08 - ИТМО 1 стали посылать задачу K. Цитата из их первого решения:

if (rand.nextBoolean()) {
  out.println("Aastria and Abstria intersect");

15:07 - Во втором решении команды МГУ 1 по D (с тех пор уже пришло третье) была та же ошибка, что и у всех остальных команд в этой задаче - не хватает промежуточной вершины в замыкании Клини.

15:00 - Осталось 10 минут. В последние минуты посылают в основном задачу B.

14:55 - В предпоследнем решении команды Saratov SU 1 в задаче B не разобран крайний случай - когда нужно набрать вес 0. С тех пор, как я это обнаружил, пришёл ещё один сабмит, поэтому я могу теперь написать о результате предпоследнего :)

14:53 - А самое большое решение тем временем тоже у команды ИТМО 1, последний сабмит по задаче D, 10016 байт.

14:47 - Результаты конкретных посылок я не буду писать, но изменений очень много. Такое впечатление, что после заморозки команды стали делать меньше ошибок.

14:39 - Осталось полчаса до конца контеста. Уже многие команды-лидеры послали решения, и некоторые из них прошли :)

14:11 - Результаты заморожены, но видно, какие команды отправляют решения. Я где-то на полчаса ухожу обедать, но обязательно буду комментировать конец соревнования.

14:10 - Мы прорешивали эти задачи вместе с Андреем Халявиным, у нас было на момент заморозки 10 задач - не была решена задача J :) (ну и K).

14:08 - ИТМО 1 сдаёт D, им осталась только задача K. В ней основная сложность - за O(NlogN) проверить, есть ли самопересечения у ломаной, кроме этого нужно просто аккуратно всё написать.

14:06 - Тем временем, у ИТМО 1 10 задач, они по-прежнему не могут найти ошибку в D. У БГУ 9 задач, у МГУ 1, ИТМО 4, МГУ 5 по 8 задач.

14:00 - Из комментариев: "Что у СПБ ГУ 2 с В? И есть ли сабмиты на Delphi? Спасибо" Delphi на полуфинале нет с 2007 года. Решение СПб ГУ 2 не работает на тесте из условия - приходит в 2, а не в 5.

13:57 - Из комментариев: "Что у ижгту в B?" Не очень понятно. Они находят не максимальный возможный вес, само решение похоже на правильное.

13:56 - Из комментариев: "Сколько команд проходит в финал? спасибо" Это ещё не объявлено.

13:48 - Из комментариев: "Что с сабмитом СПбГУ 4 по J?" Что-то очень странное. Оно не работает на первом тесте, падая на строчке "assert(0)", и это выглядит, как будто они не разобрали один из случаев, и оставили там заглушку. Но если это происходит на первом тесте, то зачем посылать? В любом случае, очень странно что они уже очень долго ничего не посылают.

13:46 - Из комментариев: "Насколько близки БГУ2 к сдаче B?" Сдали :)

13:45 - Из комментариев: "А сколько сейчас решений на С++ у команды ИТМО 1?" A, B, F, G, I, L.

13:43 - Из комментариев: "Насколько близки MIPT 2 к сдаче I?" Мне кажется близки, решение очень похоже на верное. У них выдаётся 130 букв Q на тесте, где правильный ответ 400 букв Q.

13:41 - Из комментариев: "What can you say about difficalties in problem I? Are there some "underwater stone"?". Да, там требуется очень много аккуратности, чтобы не посчитать некоторые пики два раза.

13:39 - Из комментариев: "Петя, а не подскажешь, что с командой БГУИР 1 (Belarusian SUIR 1) - у них уже 6 неверных попыток в задаче C". У них ошибка в тесте с большим ответом, видимо проблемы с eps. Само решение похоже на правильное.

13:36 - ИТМО 1 сдали F. Теперь, видимо, Миша Кевер будет писать K, а Гена и Нияз будут искать ошибку в D.

13:32 - Может быть, вы хотите узнать ещё что-нибудь о сабмитах? Пишите в комментариях.

13:27 - Команда МГУ 3 досдала 2 задачи за 3 минуты, теперь у них 7. Пока что всё равно кажется, что составить конкуренцию МГУ 1 за выход в финал никто не сможет.

13:22 - От СПбГУ сейчас проходит в финал третья команда.

13:20 - В этом году командам приносят шарики, если они первыми сдали какую-то задачу. Пока что 6 таких шариков у ИТМО 1, один у МГУ 4, один у СПбГУ 4, и один у УрФУ 2.

13:14 - ИТМО 1 сдают I. Не очень радостная необходимость писать решение для K всё ближе. МГУ 1 сдали F, вернулись на второе место. ИТМО 1 тут же исправили проблему с пустой строкой в D - но теперь у них та же проблема, что и у СПбГУ 4.

13:11 - Тем временем МГУ 4 и ИТМО 4 сдали по 7 задач. СПбГУ 4 уже на 6 месте. У БГУ 1 уже 8 задач, они вышли на второе место.

13:05 - Первая посылка по I в Санкт-Петербурге от команды МФТИ 2. Решение у них идейно верное, но видимо есть мелкие ошибки. Идея там такая: сначала найдём, какие линейные комбинации P и Q у нас есть, потом идём динамическим программированием одновременно с двух краёв, где состоянием является сколько P мы поставили слева, и сколько справа. O(N^3) состояний и такое же время работы. Нужно идти одновременно с двух краёв, чтобы можно было посчитать всего один раз, если какой-то префикс и какой-то суффикс дают одну и ту же массу.

13:02 - Довольно странно, что задачи F и I кажутся сложными - F сдали две команды (Ural FU 2 и Saratov SU 2), I вообще никто не сдал. Мне кажется, что I проще L, а F проще D.

13:00 - Самая высокая команда, у которой нет неверных попыток - Ульяновский ГТУ, 3 задачи.

12:57 - На первых двух местах нет изменений - 8 задач у ИТМО 1, 7 задач у МГУ 1. Дальше 6 команд по 6 задач.

12:55 - 515 решений на C++, 77 решений на Java всего среди петербургских решений.

12:48 - У ИТМО 1 тоже есть неудачная попытка по D - они не заметили, что ответ должен быть непустой. Когда я тестировал задачи, я сделал ту же ошибку.

12:45 - Команда Белорусского ГУ 1 тоже сдала L. Основная идея решения этой задачи такая: для того, чтобы заблокировать все пути из левого верхнего угла в правый нижний, необходимо и достаточно заблокировать два крайних пути: тот, что получается, если все время держаться рукой за левую стену, и такой же для правой стены.

12:43 - Проблема в решении задачи L у ИТМО 1 была просто мелкой ошибкой. Из-за того, что у них есть "if" вместо цикла, они забыли одинаково обработать момент прихода в правый нижний угол в обеих ветках.

12:40 - У СПбГУ 4 проблема с построением автомата для замыкания Клини: они забывают добавить отдельное состояние для "прочли очередное повторение", и поэтому их автомат для (cb*)* принимает строку "b", сначала переходя по переходу "не брать ничего" для (cb*)*, а потом возвращаясь по переходу "взять еще одну" для b*.

12:38 - ИТМО 1 сдали L. СПбГУ 4 прошли чуть дальше, до такого теста:

(cb*)*
b

12:36 - Оба решения команд МГУ по J - конструктивное построение ответа.

12:33 - МГУ сдаёт C и J за две минуты, и выходят на второе место. МГУ 4 сдаёт J и выходят на четвёртое место.

12:31 - Задача D основана на стандартном построении автомата, который принимает только строки, удовлетворяющие заданному регулярному выражению. Чтобы автомат получится маленьким, в нем нужно сделать eps-переходы. Дальше у нас есть два автомата, и мы делаем граф, вершины которого - пары состояний автоматов, и есть переходы стоимости 0 и 1, и запускаем модифицированный поиск в ширину.

12:30 - СПбГУ послали D, но не проходит такой тест:

b*a*
a

12:27 - Как-то не очень решают сегодня команды Саратова - не больше 3 задач у них. Надеюсь, ускорятся :)

12:23 - Вот тест, который у них не работает. Похоже, у них не работает, когда ответ 1?..

15 12
....#.......##.
###.##.#.##..#.
..#..###..##...
.###..#..####.#
.#.##.##..#.#..
....#..##...##.
#.####.#..#..#.
..#....#.###.#.
#...######.#.#.
..###.##.....##
.##.#.#..#.#..#
........##.##..

12:19 - У ИТМО 1 неудачная попытка по L. Главная идея в решении у них есть, но вот детали видимо не доделаны.

12:15 - 201 команда сдала хоть одну задачу (все они сдали задачу A), 114 команд сдали задачу G.

12:14 - Самое большое решение из уже отправленных - решение команды Ижевского ГУ 2 по задаче G на С++ - 4110 байт. Довольно мало.

12:00 - Не открыты четыре задачи: D, I, K, L. D и K - стандартные алгоритмы, но много писать, I и L нужно придумать, но писать меньше.

11:59 - У команды ИТМО 1 три задачи из семи сданы на C++: A, B, G - видимо, их писал Гена. Давно ничего не сдаёт МГУ.

11:56 - ИТМО 1 сдали B, избавившись от приближённой части. 60 штрафных минут потрачено на 3 неверные попытки, плюс довольно много времени за компьютером.

11:49 - у ИТМО 1 третья неудачная попытка по B, проблема с 1000 команд остаётся.

11:46 - СПбГУ 4 сдали B с первой попытки, у них тоже 6. Отставание 86 минут.

11:42 - ИТМО 1 исправили проблему со stop, но оставили приближенный поиск весов за 666 шагов, и теперь им не хватает 1000 шагов.

11:41 - Их перебор работает за 140 миллисекунд на самом медленном тесте.

11:36 - Открыта ещё одна задача: F, её сдала команда Ural FU 2. Сама задача - просто перебор, без особых ухищрений.

11:33 - МГУ 1 сдаёт B, теперь 6-5-5, СПбГУ обгоняет МГУ на 16 минут. Решение по B у всех успешных команд одинаковое: сначала уменьшаем вес до нуля, потом наращиваем до максимума, запоминая все n весов, потом перебором всех подмножеств находим нужный вес и уменьшаемся до него.

11:31 - Решение задачи J у ИТМО 1 конструктивное. Слева тратим почти все прыжки по 3 (туда-обратно-туда), справа тратим все прыжки по два (туда-обратно), получаются три случая в зависимости от количества оставшихся прыжка по 3 (0, 1 или 2).

11:28 - Открыты две новые задачи: ИТМО 1 сдали J, МГУ 4 досдали B. Единственное изменение в их решении - ответ на первый запрос :)

11:27 - МГУ 3 досдали C, избавившись от eps как ИТМО 1 - деля в конце на НОД.

11:26 - Две команды по 5 задач, отставание 70 минут.

11:25 - СПбГУ 4 сдали C. У них решение очень аккуратное - в целых числах.

11:22 - Что-то посылок стало очень мало, одна в минуту. Первые три места те же.

11:20 - У команды МГУ 4 по задаче B решение почти правильное, но они неправильно обрабатывают самый первый запрос - отвечают на него "decline", и поэтому вообще не знают, какое число является текущим.

11:18 - Проблемы с точностью продолжаются. Они уменьшили eps до 1e-14, и теперь выводят пустой файл - не находят никакого подходящего рационального приближения.

11:16 - У команды МГУ 3 ("Тапирёнок") по задаче C как раз, похоже, проблемы с eps - неправильный ответ в тесте с большим знаменателем.

11:11 - Теперь ИТМО 1 получили неправильный ответ по B. Я на этом уже один раз обжёгся, но опять скажу, что до правильного решения довольно далеко. Во-первых, они неправильно поняли формат обмена с проверяющей программой (говорят stop после accept, а не вместо него), во-вторых, у них приближённое решение для случая, когда есть совпадающие числа - пытаются по количеству раз, когда прибавляется какое-то число из первых 666 шагов, оценить количество таких равных чисел. Хотя, может быть, это и работает.

11:07 - Первые три команды те же, но теперь в другом порядке - из-за чистой сдачи МГУ вышли на второе место с четырьмя задачами.

11:04 - У первой команды Петрозаводского ГУ 1 странное решение по C - считают, что ответ либо целый либо полуцелый. На самом деле там знаменатели до ста тысяч. Собственно решение такое - отсортируем отрезки, бинарный поиск по ответу, пытаемся для каждого отрезка поставить его подотрезок как можно левее. Соответственно, возможные препятствия - сколько-то копий ответа влезло целиком между двумя целыми точками, а копий может быть до ста тысяч.

10:58 - Прошло 50 минут, первые три места 5-4-3 задач. Дальше должно идти помедленнее. Надеюсь. Иначе задач не хватит.

10:56 - У СПбГУ 4 задачи, сдали E. Решение стандартное: идём по возрастанию степени 10, для текущей степени 10 рассмотрим все мешки с достаточно мелкими монетами, и берём жадно от самого большого мешка к меньшему, пока не наберём достаточно, чтобы обнулить текущую цифру, потом переходим к следующей степени 10.

10:52 - Добавили модуль, прошло. У них решение проще, чем я видел раньше - вместо того, чтобы использовать eps и мучиться с подбором правильного значение для него, они без eps выбирают наилучшее рациональное приближение, а потом делят числитель и знаменатель на их наибольший общий делитель, чтобы выбрать нужное приближение из равных. Здорово!

10:49 - У ИТМО 1 неудачная попытка по C. До правильного решения пока далеко. Текущая основная ошибка - забыт модуль. В задаче нужно из числа в double получить рациональное число, и при проверке, на сколько отличается приближение от самого числа, они просто их вычитают, забывая взять модуль.

10:47 - По задаче H очень чёткая картина - все решения на C++ которые используют квадратные скобки для чтения из map получают TL, все остальные решения проходят. Moscow SU 1 сразу написали нормально, вышли на третье место.

10:45 - Пока что наборы задач монотонны - у всех команд с одной задачей только A, две задачи - A и G, три задачи A, G, H.

10:43 - По три задачи у СПбГУ 4, БГУ 1 и КБТУ 1. МГУ отстаёт.

10:40 - И четвёртая задача у ИТМО 1 - задача E. Тоже на Java, значит Гена готовится писать другие задачи :)

10:39 - Тем временем есть посылки по задачам C, F, L - но проходят пока только те три, которые сдали лидеры.

10:38 - Тем временем две команды по 3 задачи, 5 команд по 2 задачи.

10:36 - Оказывается, дело было не просто в map - по умолчанию квадратные скобки создают новый элемент, и соответственно получалось слишком много элементов со значением 0. Исправили квадратные скобки на find() - прошло.

10:31 - По задаче H: У ИТМО 1 решение на Java, и использует HashMap (из маски четностей по каждому символу в количество), а у СПбГУ на C++ и использует map - и у них Time Limit Exceeded из-за лишнего логарифма!

10:29 - У ИТМО 1 третья задача - H.

10:29 - Условия: http://neerc.ifmo.ru/information/problems.pdf

10:27 - у ИТМО 1 тоже две задачи. G - 20 строк, A - 22 строки. Все четыре упомянутые задачи на C++ - значит у ИТМО 1 их писал Гена.

10:25 - Решение задачи G СПбГУ - 17 строк, решение задачи A СПбГУ - 26 строк (кроме шаблона).

10:23 - у СПбГУ уже 2 задачи. Вообще сегодня много не очень сложных задач, начало контеста будет интересным.

10:21 - ИТМО 1 тоже сдают G. Еще 8 команд сдали A.

10:18 - Первая посылка! СПбГУ 4 сдали задачу G - одну из самых простых.

10:10 - 12 задач.

10:09 - Начали!

10:04 - Контест пока не начался, последние команды рассаживаются.

09:59 - Полуфинал проходит в четырёх городах одновременно: Санкт-Петербург, Барнаул, Ташкент, Тбилиси. Участники: http://neerc.ifmo.ru/regional/teams.html.

09:56 - Результаты будут здесь: http://neerc.ifmo.ru/information/standings.html.

09:53 - Конкурс прогнозов на SnarkNews: http://srv.snarknews.info/~ejudge/showvote.cgi?data=neerc2012. ИТМО:СПбГУ:МГУ 24:5:0.

09:41 - Команды пока ещё рассаживаются по местам.

This post will contain the blog for NEERC 2012 - refresh it to get new comments. The comments will be in Russian, you can try Google Translate to read them.

Saturday, December 1, 2012

NEERC 2012

Tomorrow is the day of ACM ICPC Northeastern European Regional Contest - probably the strongest semifinal ACM ICPC contest of all, home for 7 of the last 13 world champion teams. Best teams from Russia and ex-USSR, except Ukraine, gather in St Petersburg to select those who will go to the world finals, which will happen in St Petersburg as well this time, in July 2013.

There are many strong teams this year, but there are three teams that stand out (in my opinion): SPb NRU ITMO 1 (touristmikhailOKniyaznigmatul, combined TopCoder rating 8957, tourist and niyaznigmatul on the picture above, taken today at the practice session), SPb SU 4 (Dmitry_Egorovkuniavskiyeputons, combined TopCoder rating 8197) and Moscow SU 1 (SergeiFedorovSergeiRogulenkow_AleX_w, combined TopCoder rating 7877).

I will be doing a live blog about the contest tomorrow, here at http://petr-mitrichev.blogspot.com/. The blog will be in Russian since most people watching the contest speak Russian, and I hope the Google translation won't be too bad :) Join me at 10am Moscow time tomorrow (Sunday, December 2, 2012). Time in other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=NEERC+2012&iso=20121202T10&p1=352&ah=5.

Wednesday, November 21, 2012

SRM 561 Screencast

Here's the recording of myself solving TopCoder SRM 561.

Sunday, November 18, 2012

Joy of solving easy problems

Here's a problem from a recent Open Cup contest:

The similarity of two strings is defined as the length of their longest common subsequence. That, in turn, is defined as the longest string that can be obtained from both strings by dropping some characers. For example, the similarity of strings CATGT and GACTT is 3, as they have common subsequences of length 3, ATT and CTT, but no common subsequence of length 4.

You are given a string consisting of letters A, C, G, T (by far the most popular background for string problems these days :)). You need to find another string consisting of those four letters, and of the same length as the given string, that is least similar to the given string. Of course, there might be many such strings - for example, for CATGT discussed above there any many strings of the same length with similarity 1, like GAACC or TAAAC.

Can you solve it quickly?

This problem is not difficult, but I've enjoyed receiving "Accepted" from the judging system for this problem a lot. Most contests need easy problems, and it is so much better when those problems are not "easy because you just have to implement what's described in the problem statement", but "easy because you can just figure it out quickly".

Saturday, November 10, 2012

Results of "kill backtracking" contest

More than two years ago, I've launched a contest to crease the best (worst) testcase for a backtracking solution for a minesweeper-like problem. Rules are at http://killbacktrack.appspot.com/rules.jsp, and the contest site is at http://killbacktrack.appspot.com/.

The best testcase was actually found quickly - on the same day I've posted the contest to my blog, June 11, 2010. Here it is:

...2...
.2.....
.......
.......
.......
.....8.
.......

The trick is: we set up a pattern that has many possible solutions in the upper-left corner - but, all of those solutions but one require more than two stars. And we only have two stars available here because we have an 8 in the bottom-right corner, and just 10 stars in total - but the algorithm doesn't know and thus it tries different possible allocations of stars around 2s, then tries all possibilities for places where we don't have any adjacent digit - meaning we're free to put or not put a star there, only to find out in the end that there's not enough stars left.

This testcase requires 730272354 recursive calls. It was found by Dimon.Sobolevfelix.halimMax.Khodakshdendagorionmerettm and mbuzdalov, in that order - congratulations!

The next best testcase found requires 629909575 calls:


..2....
.2.....
.......
.......
.......
.....8.
.......

The idea is the same but we have slightly less possibilities in the upper-left corner. Before the contest, I've had a testcase with a similar idea but not as polished as these two, requiring several hundred million calls.

I know it's been a long time, but if any of the participants remembers anything about the contest, I'd like to hear your impressions :)

Here is the breakdown of the contest website visits by country:

Saturday, October 27, 2012

Petr Mitrichev Contest 10 solution ideas

Petr Mitrichev Contest 10 is over, congratulations to WJMZBMR, to an unnamed team from China, to tmt514, to UPC-1 team and to scottai1 for solving 4 problems, to flashmt for being the only one to solve problem D, and to hirosegolf for being the only one to solve problem F!

You can still solve the problems for practice at http://codeforces.com/gym/100110, and you can even start a virtual contest when you'll see that standings of other teams as they appeared at the particular time into the contest.

When making this contest, I've tried to add a flavor of exploration (as opposed to just using standard algorithms), since that actually resembles my work quite a bit. Please tell whether you liked that or not!

In particular, I like problem C the most, and I'm pretty sure it can be solved for 8x8, 10x10 or even 20x20 fields - but I don't know how. We can probably set up a challenge to solve it for 10x10. My feeling is that some statistical methods should be the most powerful here.

Here are the solution ideas. Those are not complete solutions, but I hope they can guide you in the right direction. Problem statements can be found at http://goo.gl/uIW7S. You can also find a video of myself doing analysis of this contest (without problem G) in Russian at http://youtu.be/FN6FRXiQ7JE. Please don't read below if you still want to try solving those problems yourself :)

Problem A. Asymmetric Art.
This problem can be solved with backtracking. The straightforward backtracking tries all possible subsets, but that's obviously too slow. We can do several optimizations: first, let's consider the numbers in increasing order, and when taking each number we can 'mark' all numbers that we can't take anymore because of this new number. This is not fast enough, but we can additionally truncate our search by saying 'if we've reached number x, then we'll take not more than answer[n-x] more numbers', where answer[y] is the number of items in the largest quasi-symmetric-triple-free subset for n=y. Then we can find all answer[] values in under one minute, and then send a program that has all answers hardcoded for judging.

Problem B. Lots of Combinations.
We need to do two things: find (n,k) modulo 10**10, and check if (n,k) is greater than or equal to 10**10. The second part is relatively easy - if k <= n-k, then we can incrementally compute (n,1), (n,2) and stop as soon as we exceed 10**10. For the first part, we notice that it's enough to compute the answer modulo 2**10 and modulo 5**10, and then use the Chinese remainder theorem. Computing the answer modulo 5**10 is done by first calculating the power of 5 in (n,k) separately, and then calculating (n,k) with all powers of 5 removed from all numbers using the fact that we can now use division and thus just need to calculate factorials (skipping numbers divisible by 5) modulo 5**10, and numbers modulo 5**10 is a periodic sequence.

Problem C. Curiosity.
I'm pretty sure there are lots of different approaches that work in this problem. The two main directions I'm aware of is finding large blocks of data without unknowns and combining them together, or using various dynamic programming approaches that consider all possibilities. My solution is of the second kind: assume we've chosen the 6x6 field. We can then use dynamic programming to find the minimum possible number of contradictions in the input data (places where we know the color of some cell but it's different from the actual cell we're on). Now I use simulated annealing to find the 6x6 field that has zero contradictions. Of course, since all input files are given to you, you can do this without any time or memory limits and then just submit the discovered answers.

Problem D. Domination.
Since one of the dimensions is small (up to 10), we can do dynamic programming using a cut in that dimension as our state. More specifically, suppose we have filled first k columns and first p cells in the (k+1)-th column. Then we're only interested what happens on the first p cells in the (k+1)-th column and the last (n-p) cells in the k-th column. Each cell can be in four states (has '1', has '2', has '0' and doesn't have an adjacent '2', has '0' and already has an adjacent '2' (let's call this state '3')), yielding 4**10=2**20 states, but it turns out we don't need all of them - some pairs of adjacent cell states are not useful: '21' and '11' can always be replaced by '23', and '20' is plain impossible. That brings the number of states down significantly, but the program is probably still too slow. The final touch is to notice that things become periodic if we fix n and increase m.

Problem E. Easy Learning.
This one probably has even more different solutions than C. There is a lot of theory for this kind of problem that I don't want to recite here, my solution was using gradient boosting.

Problem F. Hash.
There are two main approaches here. One is called Pollard's rho algorithm, and does not depend on the hash function much, the other actually uses the specific hash function we use. Consider values x_i = hash('1000 zeroes but i-th character is 1') - hash('1000 zeroes'). Then we need to find two disjoint subsets of x_i with the same sum. Let's do the following trick: sort all x_i, and take y_1=x_2-x_1, y_2=x_4-x_3, y_3=x_6-x_5, and so on. It's not hard to see that now we have 500 numbers (2 times less), but the numbers themselves are about 1000 times less on average, and we still need to find two disjoint subsets with equal sums. Repeating this several times gets us numbers that are so small that two of them are bound to be equal. This problem has some very tricky cases when b=2 - you should watch out for those!

Problem G. RLE Size.
Here, you just need to carefully consider all cases. Each block of consecutive '?' signs can be solved on paper, based on what's to the left of it and what's to the right, and then you can just implement the formulas you've discovered on paper in your program.

Problem H. Good Students and Bad Students.
This problem can be solved greedily. Let's go from the highest numbers to the lowest numbers, and gradually fill all groups. Whenever we encounter a student that wants to be in the upper half, we place it in the first upper half that still has empty slots, if any. Whenever we encounter a student that wants to be in the lower half, we place it in the first lower half that has the corresponding upper half completely filled, if any, and in the first free upper half slot otherwise. The proof is a bit tricky but doable.

Problem I. Tennis Scores.
This was the classical 'long statement, straightforward but long code' problem. You just had to carefully calculate the probabilities of game outcomes for each player's serve, then use those to calculate the probabilities of set outcomes, and then use those to calculate the probabilities of match outcomes. It's important to notice that set outcomes depend on who's serving first in the set.

Problem J. Three Squares.
This problem was supposed to be solved numerically. One step that you need to make to avoid falling into a trap is to realize that we're not always rotating all three squares by the same angle, however improbable that might look. Here's an example:


Then you could either just iterate over possible rotation angles with a reasonable step and check whether there's intersection (since all coordinates are integers, there's no possibility to create a particularly nasty case for that solution), or, if you want a more robust solution, you can do a search in the 3-D space of angles that repeatedly splits the search space in two, but then throw away certain branches when we can see that for all possible triples in that branch there's still an intersection.

Thursday, October 25, 2012

Petr Mitrichev Contest 10 - this Saturday!

I will be hosting Petr Mitrichev Contest 10 this Saturday (the day after tomorrow) between 15:30 and 20:30 Moscow time (other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=Petr+Mitrichev+Contest+10&iso=20121027T1530&p1=166&ah=5).

The contest will be held at http://codeforces.com/gyms. In order to take part, you need to have an account on codeforces.com. Both teams and individual participants can join. The contest itself will be at http://codeforces.com/gym/100110, but this link will be accessible only after the start of the contest.

There will be 10 problems of varying difficulty (most are quite difficult) for 5 hours. Your solution needs to be correct on all test cases to be accepted (the standard ACM ICPC rules). People will be ranked by the number of solved problems, and by total penalty time in case they're tied on solved problems, so don't be late! :) Note that in each problem you need to read the input from a file and write the output to another file - so don't read from stdin and don't write to stdout!

Feel free to ask any questions that you might have, and also please tell if there are any issues with the contest system - it's the first time I'm using codeforces.com/gyms.

Monday, October 22, 2012

Time and venue for Petr Mitrichev Contest 10

There will be an online contest called Petr Mitrichev Contest 10. Problems are all mine, previously used in Petrozavodsk trainings for top Russian teams this September but not published elsewhere. The problems are not easy, but they are of different types and thus I hope everyone will find something interesting to solve. Both teams and individual participants can join.

I'm trying to choose the best time and place for the contest. My current proposition is: 15:30 to 20:30 Moscow time this Saturday, October 27 (in other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=Petr+Mitrichev+Contest+10&iso=20121027T1530&p1=166&ah=5). Looking at the contest list at http://clist.by/ and the new Yandex contest site not mentioned there (http://contest.yandex.ru/contest/ContestList.html), all weekends are very busy, but it looks like IFMO trainings are not attended by many teams this fall and thus overlapping with it is OK.

I understand that the contest ending time in my proposition is 1:30AM in Japan and Korea and 0:30AM in China. People from Japan, Korea and China (and from Asia in general): is that too late? I'd host it earlier but there's a contest on acm.timus.ru that ends at 15:00 Moscow time that was very popular last year (http://acm.timus.ru/monitor.aspx?id=100), so I fear many contestants from Asia will take part there.

For the venue, I propose http://codeforces.com/gyms.

Please share your suggestions.

Wednesday, October 3, 2012

TopCoder Open 2012 Finals Commentary

16:09 - That's it about this TCO. See you next year! Feel free to ask me questions in comments, I'll do my best to answer.

15:57 - Marathon results! ainu7 is the champion, Psyho is second!

15:54 - Algorithm results! Both 500s and ACRush’s 250 fail. Egor, meret, RAVEman are the only non-zero scorers, in that order. Egor is the champion!

15:48 - They’ve announced design results (which were alredy known in advance), now development.

15:31 - I've taken a look at RAVEman's and andrew's 500s, and they both only consider moves by small_constant*first_vector+other_small_constant*second_vector. I fear that doesn't work for the following reason: when the vectors are very long, close in length to the size of the board, there can be two cells that can only be reached from one another via a linear combination with larger coefficients. So I'd bet on both 500s failing.

15:29 - They are starting announcements, but they usually do other tracks first and algorithm last.

15:21 - Waiting for systest. Currently RAVEman with just 500 first, andrewzta with just 500 second, Egor, meret and ACRush with just 250s from third to fifth. Let's hope at least the champion has one working problem :)

15:18 - ACRush one more -25 on RAVEman's 500, kills RAVEman's 250, -25 on meret's 250. Meret has got -25 on both standing 500s.

15:18 - Egor has got -25 in the meantime as well. Still above meret.

15:17 - And gets -25. Meret is also preparing the testcase for RAVEman’s 500.

15:15 - ACRush is preparing a testcase for RAVEman’s 500.

15:13 - assuming both remaining 500s will also fail, it's Egor vs meret challenge battle. Both have made their moves, still less than 50 separates them. ACRush gets -25 on Egor's 250.

15:10 - meret bring’s down marek’s 250, RAVEman brings down iwi’s 500, Egor brings down Andrew’s 250.

15:08 - admins are giving out a prize for another contest during intermission, using loudspeakers. What an AWFUL decision!

15:07 - RAVEman preparing a large and presumably tricky case for 500.

15:05 - iwi submits 500 but I'm not sure he has at least tested for TLE.

15:03 - marek.cygan doing nothing, meret writing his 1000, his solution has “layers” in it - we had an idea that involved layers, too, so that can be a correct solution.

15:02 - most people fight with not-passing-examples in 500.

15:00 - apparently RAVEman's 250 is wrong, and he's fixing it... And he resubmits!

14:59 - five minutes before the end. Marek has submitted and resubmitted his 250. I’m betting on many last-second submissions.

14:52 - actually nika’s hypothesis seems to be true and it’s even not hard to construct that ordering: let’s try all possibilities for the first vertex. Then, at every step the next vertex can be constructed by doing the following: if a vertex has more edges to the already constructed vertices then it’s closer to the last marked vertex. Also, if a vertex has less edges to the vertices yet to be constructed, then it’s also closer to the last marked vertex. And the only way both those numbers can be the same for two vertices is when they’re isomorphic. So we just reconstruct the ordering greedily.

14:45 - meanwhile, andrewzta and RAVEman have submitted the 500. I have a bad feeling about andrewzta's one, though, as he has probably patched his solution quickly to pass the sample case but he couldn't rewrite a large part of his solution since I've seen it.

14:44 - if that's true, then the solution is to handle groups of isomorphic vertices at once, and then the number of states will be really small - just linear.

14:42 - nika has the following conjecture for 1000: omitting isomorphic vertices, the ordering of vertices is uniquely determined up to a complete reversal.

14:41 - andrewzta's medium seems far from completion - he iterates over pairs of vectors but his check if the given pair of vectors gives a symmetry is too simple.

14:38 - shangjingbo’s 1000 is not working only on the last example case, which is huge. Poor guy :(

14:34 - RAVEman optimizing his 500, it’s working in 0.9s on what seems to be close to worst case. Will he submit soon?

14:29 - ACRush coding 500, meret coding 1000.

14:27 - Rustyoldman reports that iwi and andrewzta are coding their 500s.

14:18 - Meanwhile, ACRush resubmits 250. Current standings: Egor (with resubmit), RAVEman and meret (no resubmit), andrewzta and ACRush (with resubmit). ACRush has also opened the 500. RAVEman is coding on 500 and shangjingbo is coding on 1000.

14:15 - About 1000: maybe something like this can work - let’s start putting numbers from 1 to N. After we’ve put numbers from 1 to K, all that matters is which vertices are assigned the last D numbers, and which vertices have an assigned number at all. And because of the restrictions, I’d hope that the number of states will be quite small. But I’m not sure how to estimate that.

14:08 - Rustyoldman reports that nobody is still coding on 500 or 1000. meret submits 250.

14:06 - By the way, bmerry was test-solving 250 and 1000 in this round, and it took him 12 and 44 minutes respectively.

14:05 - RAVEman submits 250 as well. I’m trying to think about 1000...

14:02 - andrewzta submits 250, iwi gave up on 1000 and opened 500. ACRush went to 1000 after 250. Marek.cygan gave up on 500 and went to 1000. It’s 25 minutes into the contest and it’s weird we have just 3 submissions on the 250.

13:58 - about 250: First, we can forget about E by XORin S and E, and just making player A’s goal to achieve all zeroes. How can player A win? The only way is that the entire string has just one segment of consecutive ones. But how could B allow to make that happen? If the string has length of at least 5, it looks like B can always prevent that on his move, so when length is at least 5 we should just check if A can win in one turn, and when length is at most 4, the number of states is just 16 and we can analyze the entire game using the usual means.

13:55 - meanwhile, Egor submits and resubmits the easy, adding one more small “if” clause, ACRush submits the easy a bit later but has higher score because of Egor’s resubmit. Everybody who’s opened 500 and 1000 is working on paper.

13:51 - I’ve test-solved 500 before this contest. The basic idea is - any good tiling is defined by two “basic” shift vectors. In fact, if we fix the two basic shift vectors, then all vertices are split into groups of equal vertices, and we just need to check that all vertices in each group have the same color (it won’t be a problem to form a connected piece afterwards). Now all that remains is to iterate over all possible pairs of shift vectors and carefully check everything. This can be simplified further by noticing that we can always choose one of the basic vectors to be horizontal (but it might be up to size^2 in length then).

13:50 - formal problem statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763920&start=0&mc=2.

13:47 - 500: A good tiling of the plane that is split into grid cells that are colored black or white is such tiling where each piece is a connected block of cells, all pieces are equal (will coincide after some transition), including colors, and the tiling itself is periodic (for each three tiles X, Y, Z there’s a tile at Z+(Y-X)). What is the smallest possible size of piece of a good tiling which has a given rectangle as its part?

13:45 - 1000: you are given a connected undirected graph with M vertices, and must assign distinct numbers from 1 to N (N >= M) to its vertices so that adjacent vertices have numbers differing by at most D, and non-adjacent vertices have numbers differing by at least D+1. How many ways are there to do that? N is up to 100, M is up to 50, D is up to 8.

13:43 - marek goes for 500, iwi and shangjingbo go for 1000, everybody else for 250.

13:41 - 250: you are given two strings S and E of the same length, consisting of ‘0’ and ‘1’ characters. Player A can (but is not forced to) choose its substring and change all ‘0’s to ‘1’s and vice versa. Player B can (but is not forced to) do the same for just one character. Player A’s goal is to obtain string E, and player B’s goal is to prevent him from doinh so. What is the minimum number of turns he needs (assuming both play optimally)?

13:37 - everything looks fine this time. Two minutes before start!

13:35 - based on this, spectators propose a new strategy: if meret and ACRush submit a problem very quickly, code maximum flow _before_ opening it :)

13:34 - ACRush has apparently been coding most of this time, implementing Dinic algorithm for maximum flow.

13:28 - not much happening now, people are relaxing, admins say everything will be fine this time :)

13:17 - Egor and andrewzta playing air hocket. Meret, [[iwi]] walking around the room. marek.cygan talking with friends. ACRush looked at something on a laptop and went walking with a surprised face. RAVEman talking with friends as well. Can’t find shangjingbo in the arena.

13:14 - the problems turned out to be more serious than expected. The new start time is 13:40. Hysterical laughing from contestants :)

13:12 - it looks like the contest won’t start at 13:15, too. The technical issues still unresolved. This must be a very nervous time for all contestants.

13:05 - admin announcement: The match will start at 13:15.

13:02 - Egor and andrewzta are playing "Cities": each player should name a city that has not been named before that starts with the last letter of the previous named city. So far: Moscow, Warsaw, Wrozlav, Voronezh, Hurghada, Athens, Sarajevo, Osaka, Astana, Amsterdam, Malmo, Orel, Ljubljana, Astrakhan, Novosibirsk.

13:00 - marek.cygan: "The winner will be the one who can find the problemset".

13:00 - 250, 500, 1000. No news on contest start time.

12:59 - it looks like the contest start is postponed, there’re some technical issues.

12:49 - 10 minutes before the start. Andrewzta showed up, now almost everybody is coding the easy problem from the wildcard round for practice, except meret who’s writing max flow again.

12:44 - Everybody is preparing except Egor and andrewzta - the two Java coders. One doesn’t need much preparation when there’s no necessary bolierplate :) Egor is already ready, andrewzta not yet here.

12:35 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Finals. The round will start in about 25 minutes. I will update this post with new comments.

TopCoder Open 2012 Finals preview


This year's TopCoder Open finalists are a very diverse group of people. The most telling statistic, in my view, is the time when they first acquired 3000+ rating on TopCoder (not surprisingly, all of them did at some point :)):
So we have four people that I'd call veterans, playing the TopCoder algorithm games at the top level for at least five years, and that group is clearly separated from the other four, who have only reached the top recently. None have been the TopCoder Open champion yet, though!

Here are the micromatch scores between the today's finalists (the first number is how many times the person on the left has been ranked higher in rated TopCoder rounds, the second number is how many times the person on the top has been ranked higher):

HandleACRushmarek.cyganandrewztaEgormeretRAVEmanshangjingbo[[iwi]]Average
ACRush0/068/2360/2798/3715/285/1430/270/982%
marek.cygan23/680/051/5173/536/657/1813/1141/1356%
andrewzta27/6051/510/069/536/643/207/936/1453%
Egor37/9853/7353/690/016/1890/6741/1471/3651%
meret2/156/66/618/160/015/1415/918/1149%
RAVEman14/8518/5720/4367/9014/150/039/1770/4142%
shangjingbo2/3011/139/714/419/1517/390/014/2534%
[[iwi]]9/7013/4114/3636/7111/1841/7025/140/034%

A funny aspect of yesterday's Wildcard round was that fourth-placed people from both Semifinals advanced, meaning that we'd get just the same set of finalists if four advanced from each Semifinal and there was no Wildcard. Historically, Wildcard round advancers has won TopCoder tournaments once (tomek in TCO 2008), got second place twice (ZorbaTHut in TCCC 2004, JongMan in TCO 2007).

What strategy would people use at today's finals? Judging from the semifinals, [[iwi]] will go Hard-Easy-Medium while everybody else will use the usual Easy-Medium-Hard order. I'm pretty sure the TopCoder admins want to make sure at most one person will solve all three problems, which might well in practice mean nobody will solve all three, so starting with Hard (or doing Easy-Hard-Medium) does look like a viable strategy. I'd propose Easy-Hard-Medium switching to Medium if Hard is not solved (and it's not clear how much is left) about 30 minutes before the end.

Also take a look at vexorian's finals preview at http://community.topcoder.com/tco12/our-algorithm-finalists/.

What other stats on finalists would you like to see? :)

TopCoder Open 2012 Wildcard Commentary

19:53 - That’s it for today! Join us tomorrow for the coverage of the ultimate round - the finals! http://www.timeanddate.com/worldclock/fixedtime.html?iso=20121003T13&p1=867.

19:52 - It’s easier to tell which solutions passed than which failed :) iwi’s 1000, meret’s 500, SergeiFedorov’s and dzulgakov’s 250s. That’s it. iwi and meret to the finals!

19:49 - it looks like most 250s were indeed brought down by d=2. The results are being announced now!

19:40 - Kankuro also loses 25 in the dying minutes, on Romka's 500.

19:39 - both meret and Romka got -25 from Dmitry_Egorov's 500.

19:36 - and meret brings down SergeiFedorov's 500. Will we have two non-zero scorers to advance to the finals? :)

19:35 - Romka brings down sdya’s 500.

19:34 - dzhulgakov brings down Dmitry_Egorov's 250.

19:34 - sdya is not reading solutions, seems to have given up.

19:31 - Kankuro brings down sdya’s 250. What about 500s?

19:30 - Challenge is on! Surprisingly, no blind challenges. SergeiFedorov brings down _Romka_’s 250 and meret’s 250, but it seems that he reads them.

19:26 - Apparently iwi’s easy tries to approach (0,0) from (x,y) somewhat greedily. Is it an obvious failure or is that greedy actually some kind of gcd?.. We’ll find out soon. His code contained return “I hate math”; at some point :)

19:25 - Last seconds of coding phase were quite eventful - [[iwi]] submitted easy and SergeiFedorov resubmitted medium. [[iwi]] is the current leader.

19:24 - _Romka_ resubmits the medium, and drops to the last place. Yeah, I’d guess there’s plenty of space for bugs there as well. Looking forward to challenge phase.

19:19 - not much more action, just 4 minutes left. Everybody except iwi has 250+500, iwi has just 1000.

19:14 - SergeiFedorov submits the medium after giving up on the hard and it’s the fastest by far! He’s now in first place.

19:13 - apparently the sample cases for 250 don’t include the “all coordinates odd” case (for example d=2). I predict a lot of challenge fun :)

19:11 - iwi’s 250 is not working, he’s debugging.

19:06 - we’ve missed that dzhulgakov has resubmitted the 250. Promising for challenge phase?.. It looks like challenges will be very important if there’s nobody with 3 tasks.

19:04 - 20 minutes left. I’d say iwi is actually in a great position, as most competitors can’t get their 1000 working - many already coded up some DPs.

19:03 - SergeiFedorov gave up on hard and moved to medium.

18:59 - I guess we can speed things up by considering where will the first letter of large string go. It’s either removed at some point, in which case we get a suffix of large string and the same small string, or mapped to the first letter of the small string. So this can get us a DP on (suffix of large, suffix of small), although it’s not clear to me if we can still manage not to overcount solutions where one of consecutive letters is removed several times. Maybe we should add something like “last removed letter” to the state?.. Anyway, it’s too late to think about this.

18:57 - I can’t see iwi’s solution now, but wata tells its complexity is 50^3, not 50^6 as my proposition below.

18:54 - Currently _Romka_, sdya, Kankuro, meret, Dmitry_Egorov and dzhulgakov submitted easy and medium (and all moved on to the hard), [[iwi]] submitted hard and moved to the easy, SergeiFedorov submitted easy and moved to hard.

18:49 - So the rough approach for the 1000 is: let’s count the number of ways to obtain a substring of the small string from a substring of the large string. We do that by checking which character will be removed last, which leaves us with two substrings of the large string that should be matched somehow to the small substring, so we also have to check all ways to split the small string into two. One challenge is not to count things twice with consecutive equal letters, but that should be doable although I’m too lazy now to figure out how. Another challenge is running time: currently we have something like (50^3/6)*(50^3/6) - (the number of ways to choose a substring and a letter in it)*(the number of ways to choose a substring and a split point in it), which is about 500 million which might be too slow. But in reality we have more restrictions like length of large substring should be at least length of small substring which divides everything by 2 more, and the same for both halves which should divide by something like 2 further, bringing the total running time under control?..

18:43 - About 1000: let’s go from the long string to obtain the short string. The only way we can confuse two removals is when there’s a string of consecutive equal letters in the long string. In that case, removing each of those letters produces the same string, so we should always remove the first one of them. Still don’t know what to do next...

18:39 - forgot to post the link to statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763830&start=0&mc=2

18:36 - 250 and 500 solved by Romka.

18:35 - the complexity of that solution is 50*2500 (maximum number of steps)*50(number of equations to check on each step). We can check each equation in O(1) time using hashing.

18:30 - 500 does look straightforward-ish. We will construct all strings from the end. We take any equation, and if one of its parts has more letters known in the end than the other, we reconstruct the missing letters. We repeat this until we can’t reconstruct anything, or until one of the strings is of length more than 2500. In the latter case, there’s no solution (we’ve entered an infinite cycle), and in the former case, our current suffixes are a valid solution, and the smallest one.

18:28 - Meanwhile 7 people submitted easy and [[iwi]] works on hard. Also SergeiFedorov switched to hard after easy.

18:25 - Here’s why the solution for the easy works. If we have a jump by (a,b), then we have jumps by (2a,0) and (0,2b), and also jump by (b,a). Thus, we can get jumps (2g,0) and (0,2g). Then if there’s a jump (2kg, (2m+1)g) then we can get to (0,g) using those two jumps. Otherwise, all jumps are ((2k+1)g,(2m+1)g) and we can get to (g,g) but can’t get to (0,g).

18:22 - 500: We have a system of equations a_i = b_i + c_i, where a_i and b_i are variables, c_i are constants, + is string concatenation (like s = t + “a” and t = u + “b”). We need to find the minimal sum of lengths of its solution.

18:19 - So together with Egor we kind of figured out the 250. Suppose the gcd of all coordinates of all possible jumps is g. Then there are two cases: if at least one jump has an even coordinate (after division by g), then we can get to any point where both coordinates are divisible by g. If all jumps have odd coordinates after division by g, then we can get to any point where both coordinates are divisible by g and their sum is divisible by 2g.

18:09 - Apparently my thinking gets slower as the day comes to an end. It’s kind of obvious that you have to generate all integer vectors of length sqrt(d), but where to go from there?..

18:07 - Romka has just submitted 250! I still have no clue how to solve it.

18:02 - 1000: let’s consider sequence of strings good if for each applicable i s_i is s_{i + 1} with one letter erased. You have two strings, how much different sequences exists with this two string as first and last element? String lengths are up to 50.

18:00 - 250: one starts at (0, 0) and can jump to other integer points. Each jump should be exactly sqrt(d) in length. Is it possible to get to (x,y)?

17:56 - meret has coded max flow to warm up and in case it shows up at the contest. Three minutes before start.

17:44 - One more comment from Gennady Korotkevich (made before the semifinals) - he said that almost anyone could win, but if forced to bet on somebody, he’d bet on meret. Well, now meret has to qualify from the Wildcard to live up to the expectations :)

17:43 - 250, 500 and 1000.

17:41 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Wildcard Round. The round will start in about 20 minutes. I will update this post with new comments, and so will Egor who’s joining me again.

Tuesday, October 2, 2012

TopCoder Open 2012 Semifinal 2 Commentary

15:03 - that’s it for Semifinal 2. Join me later today for the coverage of the Wildcard round at http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO+2012+Wildcard&iso=20121002T18&p1=867!

15:01 - results: dzhulgakov’s 275 and 950 fail, kalinov’s 500 and 950 fail, marcina007’s 500, wata’s 500. shangjingbo, marek.cygan, andrewzta to the finals, meret, Kankuro, Dmitry_Egorov, dzhulgakov to the wildcard.

14:48 - kalinov’s 500 will also fail.

14:42 - dzhulgakov says his hard solution fails.

14:40 - waiting for systests.

14:38 - nika says that several mediums will time out, and contestants themselves know that. Meanwhile andrewzta’s 500 goes down, and there are two more -25s.

14:37 - Right! Now everybody can see the submissions and it’s actually non-competitors who look at leaders’ solutions. (14:37:34) qiuiuu> spectators are interested in top submissions actually.

14:35 - no more action yet, we’re in the middle of the challenge phase.

14:32 - lots of people are reading shangjingbo’s and kalinov’s solutions. As in the first semifinal, solutions of leaders are attracting more interest, which looks illogical to me.

14:31 - (14:31:03) System> marcina007 unsuccessfully challenged shangjingbo's 500-point problem.

14:25 - dzhulgakov also submits the 950 with 30 seconds to go. The current situation: shangjingbo 1375, kalinov 1285, marek.cygan 1145, andrewzta 1084, dzhulgakov 1047. The only less-than-50 gap is between andrewzta and dzhulgakov. Waiting for challenge phase!

14:20 - andrewzta submits the 950. As things stand, he’s still fourth and needs two challenges to overtake the 3rd place, but solutions may fail at systest, you know :)

14:19 - Marek’s solution is the same as ours and kalinov’s. Kankuro has his solution timing out (and it has a weird “for (int t = 24; t >= 5; --t)” loop :)), andrewzta gets wrong answer and is trying to add more and more debug output.

14:14 - Marek submits the hard, 3 people with all problems now. Lining up nicely for the finals, but I’d guess there will be more submissions as the end approaches.

14:06 - pieguy opened hard abandoning his medium. wata had not opened easy, so he is either still working on medium or trying to finish hard.

14:04 - So his solution has complexity of 47 (for k) times 47*4 (for number of bad events happening) times 4 (for number of bad events on this team). The problem is solvable for much larger constraints!

13:59 - Here's how shangjingbo's solution works. We'll do inclusion-exclusion, with the basic event being “rabbit X gives a carrot to someone from his team”. Then how do we count the number of cases with T such events happening? We’ll do a DP over “first k teams, T events”. For a new team, we iterate over how many rabbits in that team give a carrot to someone in his own team, and multiply that by 4*3*.. to account for giving that carrot to different people on his team, and by c[rabbits][num] to account for different rabbits on the team taking part.

13:59 - Meanwhile we have shangjingbo and kalinov with all 3 problems, meret, andrewzta, marek.cygan, dzhulgakov and Kankuro with easy and medium, wata with medium only, pieguy, marcina007 and Dmitry_Egorov with just easy. wata is the only one that had not followed easy-medium-hard approach.

13:49 - Studio finalists are introduces quite loudly. Not sure how algo semifinalists could think about problems currently.

13:48 - shangjingbo submits the hard. His solution is even simpler than what we wrote below, he has just 47*(47*4) states in his DP. kalinov is writing something similar to our solution, but his solution doesn’t work on examples yet. meret is writing some solution which has a DP state of “5 numbers with sum up to 47”. Nobody else is writing code for 950.

13:45 - dzhulgakov also submitted medium.

13:44 - andrewzta is sitting with his notebook and pencil, trying to figure out 950.

13:43 - Marek has submitted the 500.

13:42 - Nothing changed during recent minutes, we are now into the second half of the contest.

13:36 - wata abandoned hard and switched to the medium instead.

13:34 - Easy and hard are DPs if we don’t have issues in our solutions, medium does not involve any standard approach.

13:32 - Medium submissions started to flow in, kalinov, shangjingbo, meret and andrewzta currently submitted and moved on to the hard.

13:31 - actually, 16 can be replaced by 4 since we’re just interested in how many team members are receiving the carrots, not which ones. We just have to be careful to multiply by appropriate coefficients to make sure we’re counting all possibilities.

13:28 - the complexity seems to be: 47 for the boundary position, 47*4 (actually 47*4/2) for the left-to-right number, 47*2 for the right-to-left number, 2^4=16 for the subset of this team that will receive carrots, 4 for the number of carrots from this team that go to the right (all remaining go to the left), and 4 for the number of carrots for this team arriving from the right. All in all, that’s 47*47*2*47*2*16*4*4=106314752, so that should work.

13:27 - here’s our idea for 950: let’s do a DP over “how many carrots cross the boundary between team x and team x+1 from left to right, and how many cross that boundary from right to left”.

13:26 - kalinov and shangjingbo submitted medium.

13:25 - All competitors but wata submitted easy and opened medium, wata still works on hard. This commentary is brought to you by Egor, who’ll be helping me during the rest of this round.

13:25 - 950: There are n teams with 4 players each, and each team brought 0<=a_i<=4 carrots. Find the number of ways to distribute the carrots in such a way that each carrot is given from a team to a different team. All carrots are considered distinct.

13:22 - actually, that solution was wrong, as ACRush has pointed out. The correct solution is: iterate over the set of “important” bits, and then just check if there’s a number that has one important bit set and all others cleared, for all important bits.

13:13 - 500: a set of numbers is called good when all bitwise ors of its subsets are different. What is the subset of the given set of numbers that is good and has the maximum sum of elements? Egor solved it in about 30 seconds: the “good” condition is equivalent to “each number has at least one bit that is zero in all other numbers”, so we can do a DP over “maximum sum of subset of first k numbers that have the given mask of bits as their chosen bits”.

13:11 - Three submissions for 275: shangjingbo, pieguy, meret.

13:05 - Problem statements as contestants open them: http://apps.topcoder.com/forums/?module=Thread&threadID=763801&start=0&mc=2.

13:03 - it looks to be a straightforward DP. For each segment of balls, we determine whether it's possible to remove that segment completely. To check that, we iterate over which two balls will be removed the last, and they separate that segment into subproblems.

13:01 - The 250 problem: you are given n balls (n is odd), each marked with either “left” or “right”. In one turn, you take one non-boundary ball and remove it and the ball to the left or right from it, correspondingly, until there’s one ball left. Which balls could be the last one left in the end?

12:56 - announcements are done, 3 minutes before start. There are several in-form competitors in this round: meret has won Google Code Jam just several months ago, Kankuro has won Russian Code Cup a month ago.

12:49 - There are two Java coders in this round as well: andrewzta and wata. In the first round the Java coders took the first and last place :)

12:48 - There are 11 contestants in this round. Burunduk1 couldn’t come, and he told that too late to rearrange everything.

12:48 - 275, 500, 950.

12:39 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Semifinal 2. The round will start in about 20 minutes. I will update this post with new comments.