Nope, I'm too lazy to maintain both versions :)

Thanks for the contribution everyone. Sorry for the delay, I don't receive e-mails about new comments for some reason.

I'm not sure I understood you right. There's no need in additional loops as you describe. It's a standard DFS.

If you process the nodes in this order, then for example when you run dfs(2), the vertex 1 won't be visited again and dfs_low[2] = 2.

The sum of Manhattan distances over all cells: = = .

Now we need to subtract the sum of Manhattan distances with occupied cells. Suppose (x, y) is one of occupied cells, then . Since there are at most max(n, m) occupied cells, we can just sum over all (x, y).

Finally, the pairs of occupied cells were subtracted twice and we need to add them back. It's O(max(n², m²)) as well.

And don't forget that the order of cells matters, so for example the sums in the second paragraph above need to be multiplied by 2.

Try this one.

The Russian version seemed hard to understand to me as well. I probably spent more time reading the statement rather than coding the solution.

A simple link to the tag search would suffice (and be in line with the whole Web 2.0 idea of the site), but tags need to be kept consistent for that. (And they need to actually work, e.g. this doesn't find anything.)

Here are my results for N=200. (gcc 4.4.3, Ubuntu 32bit).

g++  0.899s
g++ -O2 4.733s
g++ -Os 0.413s
g++ -O2 -fno-tree-ter 0.390s

One would think that the optimization ftree-ter is broken. However it seems that it's enabled at -Os as well. In fact, the only difference in optimizations between -O2 and -Os is -finline-functions at my system. I tried turning it on, but to no effect.

Here's the relevant part of the man page:
-ftree-ter

Perform temporary expression replacement during the SSA->normal phase.  Single
use/single def temporaries are replaced at their use location with their
defining expression.  This results in non-GIMPLE code, but gives the expanders
much more complex trees to work on resulting in better RTL generation.  This is
enabled by default at -O and higher.

Very nice problem D...
Kudos to the author.

Read the problem statement carefully. The operations are:

1 1 1 1

+
2 1 1

+
3 1

*
3

I had the same line of reasoning. Would love to know the solution…

http://codeforces.com/blog/entry/1112

> k - is the length of each part
But the parts may have different lengths.

> Also in transition we should be careful with the equal numbers (I used set).
Can you explain the details? For example, how do you make sure that in the sequence (1,3,2,1,3,2) the subsequence (1,3,2) is counted only once?

OK, I figured it out. Apparently test files have Windows line endings but the input in the custom test has Unix line endings.

Yes, and my program worked correctly for the first sample when I ran the custom test. It didn't pass the pretests though. Then I added handling extra whitespace and it passed.

I think in tests for problem A there is extra whitespace. Can you check the first pretest?

Is this award displayed somewhere on the site? I was expecting to see medals or badges in laureates' profiles.

I didn't use either of these optimizations but avoided the 'strictly less' flag (so, the number of states is only 2 times less, while with these optimizations it's 48*5 = 240 times less). Still got AC…

Just to clarify: these are not bugs. 1<<42 is undefined behaviour, and the other one is also well-known.

-ffloat-store compiler flag solves the floating-point problem for me. The other one I don't have.

Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.4.3-4ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --program-suffix=-4.4 --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug --enable-plugin --enable-objc-gc --enable-targets=all --disable-werror --with-arch-32=i486 --with-tune=generic --enable-checking=release --build=i486-linux-gnu --host=i486-linux-gnu --target=i486-linux-gnu
Thread model: posix
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)

> let's talk about gay-on team
So… how many people on your team are gay?

I thought 2011 is the year of white rabbit, not red :)

Yep, now it seems to happen more frequently :)

Great analysis!
In problem E to find integer roots I just iterated over all possible roots x and for each of them over all possible coefficients c (they must be divisible by x). Knowing x and c, we can find the second root and coefficient b and check the conditions. The time is .

Look at the time that question was asked. Mike meant that during the contest the test cases are not available.

I don't think so. Can you show the code?

Wow, the tests are now available? It's very nice!

По-моему, дело не в карме самой по себе, а в засилии школоты*. Я даже в русский интерфейс перестал заходить из-за этого, тем более все равно сайт меня все время разлогинивает и сбрасывает обратно на английский. А если начинать делать ограничения в зависимости от кармы, не превратится ли CF в хабру с его жополизством, смехуечками и перепостами с реддита и фишек?
По поводу модерации: можно, например, отдельные посты удалять и делать предупреждение пользователю. Каждый у себя в профиле (и только у себя) сможет видеть, сколько у него предупреждений. По достижении определенного количества красная карточка =) Но понятно, что сейчас рук у администрации на все не хватит.


*Disclaimer для незнакомых с терминологией.

Why is negative result allowed in task E? It doesn't make sense. It's also sad that the solution using iostream doesn't pass the TL, because usually at CF it's OK to use iostream and some of us got used to it:)
But overall, the problems are very nice, thanks!

Is there a schedule for December already?

If you participate 'out of competition', then when you enter the contest you appear in room number 1 instead of the room you were assigned to. (It's a bug.) To move into your room, select it from listbox in top right corner, it's marked with a star.

Ah, yeah, sorry

Try 1 2 and 1 4

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

Ну так или иначе это баг

> у некоторых участников вместо месяца  написано время

Подтверждаю, у некоторых написан просто месяц, у некоторых месяц и число, у некоторых время. Это, думаю, не зависит от браузера.

Seems that two of the problemsetters of this round are Fefer and RAD
I don't see what's wrong with your solution either.

The idea is to assign some numbers a_i to vertices and the lengths a_i + a_j to edges. Then the condition about hamiltonian cycles will be fulfilled. To ensure the condition about different lengths, just choose the numbers a_i one by one so that it was always true that a_i + a_j ≠ a_i' + a_j'. In other words, when you choose a new number, it mustn't be equal to a_i + a_j - a_k and a_i - a_j - a_k, for any already chosen a_i, a_j and a_k. It turns out that if n ≤ 20, this process never needs numbers more than 500, so all edges have lengths less than 1000.

I haven't found the algorithm, just some observations and I don't even remember them :)

Это потому что порядковый номер Codeforces BR#40 — 41

I don't know… During the contest I came to some conclusions similar to the proof in the paper, so in principle it's possible to obtain it independently. It's only 1 page long, after all.

It's based on a theorem from this paper

It's a new Russian currency. One bourle = 100 pokeikas  ≈  0.032 laddors.

A quick search suggests that you can use the __debug__ variable. (Note that according to this, the programs are executed with -O switch.)

Мы проводим новое ребро i<->i+2, откуда следует что нет вершины j (может, даже не из цикла), соединенной с этими обеими вершинами?

Here's my solution to I, maybe it'll be useful for someone.
First note that Gray code is 'circular': the last element differs from the first one in one digit. So, we can start enumerating subsets from any position in Gray code.
Now we'll enumerate partitions recursively. Fix the minimal element x and iterate over the (Gray code of the) subset of elements which are in the same subset with x. If M is the subset of all other elements, call our procedure recursively for M. We'll obtain a 'good' sequence of partitions. Unfortunately, if M₁ and M₂ are two consequent values of M, the sequences of partitions for them could not 'glue together': the last partition obtained from M₁ can be very different from the first partition obtained from M₂. But we can always apply a circular shift to the second sequence so that it glued together with the first one. I don't know what's the complexity of this but it passed the tests.

Не все так просто, при такой замене мог появиться треугольник.

Ага, у меня обе ссылки работают, а первое сообщение вообще много где выскакивает.

When you register for the competition you are asked to read this

Сервис->Шаблоны?

> опубликованы некоторые разборы. Скоро появятся и остальные, не беспокойтесь:
Как насчет разбора H? O:-)
И да, разборы не переведены на английский. Могу помочь с этим, если нужно.

m и n не совпадают по четности

Don't use dollar signs, they are interpreted as TeX formulas ;)
If you want to show code samples, you can use, for instance, pastebin.com

(or tag <pre>)

Немного есть тут

By the way, when you registered for the contest it was written that it would be rated for everyone.

Обратный отсчет справа отстает на 3 часа.

А язык, который используется в Delphi, — это разве не Object Pascal? В последний раз, когда я его видел, это было так, да и википедия подтверждает.

Зачем мыслить 'объектно' в спортивном программировании? И в каком месте C++ более 'объектный', чем Object Pascal?

It's not true here that R_i ≤ r_j

It'll give a negative result here, so at least it should be pointed out that we must take a maximum of zero and Δ_ij.

Кстати, вокруг n скобочки лучше бы поставить :D

    int c = 3;
    REP(i, c>0 ? c : c+1)
        cout << i << endl;

Maybe I'm missing something, but where does this case belong to? (i-th bowl is the higher one)



It seems that it's case 2, but the formula will give a wrong answer.

Например, такая штука не скомпилируется:

#define all(v) v.begin(), v.end()
vector<int> x;
vector<int>* p = &x;
sort(all(*p));

Во втором случае, конечно, скобочки не нужны, но их все равно ставят во всех макросах во избежание досадных неприятностей типа такого:

#define sqr(n) n*n
cout << sqr(3+3)

Если уж занудствовать, то со строгой математической точки зрения НОД в произвольном евклидовом кольце определен с точностью до умножения на обратимый элемент.

Нет, в первом случае смысл a[i][t] такой же, как во втором. Откуда берется такая формула, хз)

Во втором варианте t — номер студента, который сидит слева.

Это какой-то очень старый gcc. В новых операция битового сдвига знаковая (пруфлинк), поэтому с отрицательными числами countSimple не работает.

Время работы countSimple должно оказаться равным ∞. Можно посмотреть на gcc --version?

По скорости, в смысле? Ну в этом ничего удивительного, вряд ли разработчики gcc придумали принципиально новый алгоритм вычисления нода)

> Все проводимые соревнования будут открыты для неофициального участия студентам и другим пользователям Codeforces, кто не участвует в официальном зачете.

Для участия вне зачета регистрироваться не нужно?

Прямо сейчас тут идет прямая трансляция финала

fixed, спасибо.

Может быть 2 столкновения одновременно в разных точках, в условии это не запрещено.

Мы говорим вот про этот случай:
"некоторые не учитывали, что может быть несколько столкновений в один момент"

Ты учитываешь :)

Нет, дело не в этом. Если столкновения происходят в абсолютно одинаковое время, то это не поможет.
Те решения, которые проходят, похоже, сортируют точки по координате (их порядок в процессе не меняется) и потом сравнивают скорости соседних. Тогда все работает.

В задаче E некоторые не учитывали, что может быть несколько столкновений в один момент. Правда, какие-то решения почему-то проходят и так, см. например 140641

BR: В начале контеста меня автоматически перебросило в комнату 1 (а должно было в 100). И еще если по задаче были неудачные попытки (взломанные или не прошедшие претесты), то во время тестирования она отображается как "Не пройдено"

За мкадом пределами твоего часового пояса тоже живут люди.

Я пишу abs(__gcd(a, b))
=)

> говорят даже можно как-то объединить арену и Visual Studio

http://www.topcoder.com/contest/classes/ExampleBuilder/ExampleBuilder.html

И что? Когда отправляешь на паскале, протокол тестирования отсутствует что ли?

Why are you writing 'codeforce' everywhere? It's 'codeforces'!

Replace 200 with something larger. The minimum path length may be upto 100*25

> даже и не знаю в чем ошибка

А свою задачу заблокировал перед этим?

Нашел классную багу, отмотайте в этом комментарии историю назад и смотрите что происходит с ответом на него

Вероятность попадания юзеров в одну комнату не зависит от того, один и тот же это человек или нет =)
Хотя возможно, он зарегил 20 ботов abc, abcd, abcde и т.д. =)

"разрешено заменить символ A_i на символ B_i в любой из строк"
"В следующих n строках заданы два символа A_i и B_i, (...), означающие, что разрешено заменить символ A_i на символ B_i"

Где здесь неоднозначность?