Однозначно на порядок лучше чем последние два Code Jam'а в плане подхода, организации, отношения. По большинству факторов лучше чем TCO (и если это действительно будет ежегодно и желания/возможностей у организаторов не убавится, то думаю скоро будет почти по всем факторам лучше TCO). К сожалению не был на Фейсбуке, так что не могу сказать. Mail.ru приятно удивили.

Maybe even Toastwoman. :)

Переносить неправильно, потому что у людей у многих запланировано время под сам СРМ. Если перенести, скажем на час, чтобы продлить регистрацию, то многие просто не смогут поучаствовать.

Через пару дней будет вот здесь: http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis.

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

Темпы регистрации говорят, что, пожалуй, все же будет. Слот субботний самый популярный, да и количество АСМ-финалистов в общей массе участников вряд ли больше чем 10%.

Сегодня 2250 лимит. На самом деле его пока еще ни разу не опускали, ну и потихоньку поднимаем.

This time it seems to be exactly this problem. The Wikipedia article even contains a link to all necessary answers (for n <= 128).

De Brujin sequence is somewhat similarly defined, but in fact is absolutely different topic.

I implemented brute force and hoped to find some regularity in answers (it failed). Then I used brute force to count the number of valid answers for different values of k. Finally, I used OEIS to find that it corresponds to the number of primitive polynomials over GF(2).

Here is an example: http://www.ncd.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf. I believe there are others as well, since the topic of "primitive polynomials" seems to be well-studied.

There is an editorial for D published (russian only at this point). It follows from it that the intended approach is able to solve such problem for any function (Ks, s) (of course given that it can be calculated quickly).

По каждому атрибуту построим точку в 3d: (first_slime[i], second_slime[i], third_slime[i]). Задача эквивалентна следующей: построить монотонную цепочку (у каждой следующей точки все 3 координаты >= предыдущей; в цепочке не обязательно столько же точек сколько во вводе) такую, что если каждую исходную точку модифицировать в ближайшую (по Манхэттену) точку построенной цепочки, то сумма будет минимальна. Можно показать, что в цепочке, которую мы строим, можно всегда считать, что у соседних точек две координаты совпадают, а третья +1 (с точки зрения сжатых координат). Отсюда простое ДП за N^3.

Так странно что ее не решили. Ты за 6-ю степень знаешь?

Чтобы прошлый коммент не отпугивал потенциальных участников, ну и просто, чтобы было альтернативное мнение, скажу, что на мой взгляд задачи отличные. Из 4-х квалификационных раундов GCJ, которые я писал, этот мне кажется самым лучшим по подбору задач.

Фейл никак не связан с количеством участников. Единственное, что room assignment совсем медленно отработал, а так вполне можно было бы еще поднимать.

Вообще успевает даже построение дерева заново на каждом шаге. Т.е. добавляем к прошлому дереву доп. ребро и просто все перестраиваем (я даже пересортировывал заново для простоты).

Предположим некоторый бит в X равен 1, а в Y равен 0. Тогда эти два бита можно поменять, не изменив X + Y и X xor Y и уменьшив X, т.е., получив лучшее решение.

Thank you for taking care of the issue!

I read second line (Java, readLine() of BufferedReader) and then parse it. If there's no line at all, readLine() returns null and attempt to parse it results in runtime error. If there's an empty line, it works fine.

Since, as I see, it was decided to rate the match (at least my rating has been changed), I'd like to ask admins to add the second line into pretest 4, problem E (and other test cases, where appropriate), and to retest all submissions.

What's so clear about that? Is "unite provinces" something that can be understood in unique way? I don't see anything wrong with understanding "make them reachable from each other via roads". I think even merge is much better than unite (but I read russian version unfortunately during the match), though still far from ideal wording.

I'd like to support the opinion on making this round not rated.

Это сборный контест из старых неиспользованных (ТопКодером) задач. В див-1 авторы misof, Mike Mirzayanov и stone.

Тогда это не очень красиво со стороны автора задачи.

Правильно ли я понимаю, что это соревнование не имело никакого отношения к ТопКодеру ?

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

Проблема в том, что если мы вырежем этот кусок пути, то закончим уже не в клетке (R', C'), а на какое-то количество шаблонов выше, а это уже не совсем то, чего хотелось бы достичь.

Yes, we can assume this. More exactly, the solution has the following structure. Let the input sequence be a[0], a[1], ..., a[N-1] and we want to construct b[0] < b[1] < ... < b[N-1]. The solution consists of several segments (st[0], fn[0]), (st[1], fn[1]), ..., (st[k-1], fn[k-1]), where st[0] = 0, fn[k-1] = N-1, st[i] = fn[i-1] + 1. For each  segment i there's some index mid[i], st[i] <= mid[i] <= fn[i], such that each b[j], st[i] <= j <= fn[i], is equal to a[mid[i]] + (j - mid[i]).

This property leads to O(N^3) solution and this is the best I was able to come with so far. Of course, something much faster is required...

Yes, you're correct, I haven't noticed we have Ruby/Python/php in the list of allowed languages. Though, as far as I understand, it's just impossible to solve some of the given problems on these languages.

In this case, it would be nice to define the subset of allowed languages such that each problem is guaranteed to be solvable on each of these languages. Then the limit can be set based on the reference solution written on the slowest language from this subset. I'm not sure if it's a good idea to include only C/C++ in this subset.

Anyway, I don't really mind how the time limits are set. It just would be nice to have a common publically available standard to set them.

[This is slightly off-topic, sorry for this.]

I've seen a similar problem at BOI'2004: http://www.boi2004.lv/Uzd_diena1.pdf (third problem). The main two differences: the limit on sequence length is 1000000, resulted sequence must be strictly increasing. I've been thinking for quite a lot on that problem and still don't have any working ideas. If anybody has clues on how it can be solved, could you please post.

"По-моему, могли бы клар и не давать. На некоторых контестах, жюри посовещалось бы и ответило "No comments". ;-)"

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

I see, the decision is reasonable since your implementation being rewritten in Java would almost certainly pass within 2 seconds. But this almost doesn't leave any space for not so optimized solutions (generally speaking, this is not necessarily a bad thing, but for this particular problem it seems that C++ coders had a significant advantage).

I think (and this is a question to Mike) it would be nice to have a kind of standard for setting time limits at Codeforces. For example, time limit must be at least twice the running time of the reference solution implemented on the slowest available language (or something like this).

Так а он на самом деле доступен, вот ссылка на все правильные решения по D:

http://codeforces.ru/contest/13/status/D

Там он немного кривой, т.к. пришлось в TopCoder Arena писать (у меня не было плюсов на компьютере).

Есть такое ощущение, что поднять ограничения не особо бы помогло. В "быстром" (N^2 * (N + M)) решении сами операции довольно тяжелые (геометрия), а в "медленном" (N^3 * M / 32) вроде операций и побольше, но сами операции (битовый and) намного легче. В итоге мне кажется разница времени работы будет буквально в 2 раза, а то и меньше.

As a clarification of my previous post, "you" meant "problem writer and/or testers".

Seems it would be nice to have a higher time limit (as even this solution required additional optimization).

Я делал совершенно то же самое, в итоге на С++ прошло за 1.7 секунды, на других же языках такое ощущение что сдать это почти без шансов. Скорее всего, это не было одним из предполагаемых решений.

Вообще с учетом того, что даже N^2 (N + M) решения требовали значительных оптимизаций, мне кажется, что более щедрый тайм-лимит по этой задаче (скажем, 4 секунды вместо 2-х) был бы более правильным.

Ну у меня вот N^3 * M / 32 в итоге прошло и в принципе без шаманств, хотя оптимизировать пришлось :)

Мне почему-то кажется, что у авторского решения такая же ассимптотика (т.е. N^2 * (N + M)).

I wonder whether you had a Java implementation for D and if yes then what was the worst execution time on a single testcase. My Java implementation timed out despite all possible optimizations I was able to come with and then the same solution on C++ passed. [My solution was N^3 * M / 32 and I understand that it's possible to solve in N^3, but still it wasn't something I liked, despite even some straightforward N^3 precalculations took around 1 second on my PC.]

Overall, the problems were nice. Thanks for the round!

I wonder what was your problem with B that leaded to so many incorrect attempts.

Thanks for the round!

I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.

Неужели правда была динамика по рваному краю в 250? Я не встречал, но вообще для 250 это было бы слишком сложно (если брать уровень сейчас, а раньше вроде бы было легче).

На ТопКодере для успешного выступления изучением множества специализированных алгоритмов заниматься (почти) бесполезно. Просто наиболее реальный результат использования задачи, которая очень сильно базируется на каком-то сложном алгоритме, который мало кто знает -- либо никто не решит, либо решат те, кто погуглят и возьмут его откуда-нибудь из интернета. Оба случая малоинтересны.

Задача на Фурье действительно один раз была, но она решалась также и алгоритмом Карацубы, причем это решение было авторским. Хотя в результате так ее решил вроде бы только Petr, а остальные достали Фурье из загашников (ну и еще Psyho вроде написал лобовое решение с ассемблерными вставками). Т.е. получилась полная ерунда, ну и фидбек по задаче был соответствующий - в стиле "одна из худших 1000-задач за все время на ТС". Так что это скорее такое исключение, которое подтверждает правило.

Иногда (но тоже редко) бывает, что задача использует какой-нибудь (относительно) малоизвестный факт. Например, в январе была задача, существенно основанная на том, что любой двудольный граф имеет реберную раскраску в кол-во цветов, равное его максимальной степени. Так что в принципе изучение сложных алгоритмов может помочь, если их детально изучать, с обоснованием, плюс если знать много разных сопутствующих фактов. Но это тоже, мне кажется, довольно редкая вещь.

Если имеется в виду, что такое решение даже на совсем маленьких тестах валилось, то это однозначно какая-то ошибка в реализации.

На самом деле все не так было. Финансирование Epam не прекращал, оно просто всегда оставляло, скажем так, желать лучшего (оно и понятно, Epam никогда не понимал, зачем им подобный проект вообще нужен). Вот команда потихоньку и разбежалась. Мы с Леной Носовой, к примеру, на TopCoder ушли. Вроде после пытались на Epam'е как-то все это реанимировать, но, как видно, безуспешно.

Спасибо за ссылку огромное! У меня тоже еще та ностальгия, все-таки два с половиной года жизни прошло там... Иногда после и хотелось посмотреть, как оно было, вспомнить что-то, да негде было.