like last contest :D

AND were made hacking easy

4 . score distribution .

yeah.. me 2:)

I bet there will be with permutations

So short, like yesterday? :)

I really need to know it before the contest. It's a matter of strategy, at least for me.

codeforces копит силы на контест:)

It's published)

Не знаю, зайдет ли, но все же. Заметим, что k = 8 в худшем случае. Переберем все p[x]. Для каждой перестановки проверим, выполняются ли условия. Соответственно если все норм, то к ответу + 1. Для остальной части домов, ответом будет (n — k) ^ (n — k). То есть каждой p[x] можно проставить (n — k) значений. Перемножаем полученный результат с предыдущим ответом. Не забываем про модуль. Выводим ответ.

Ответ является произведением двух чисел. Количество комбинаций "хороших" домов от 1 до k и количество комбинаций "плохих" домов от k+1 до n. Каждый из плохих домов по условию задачи может вести только в другой плохой дом, считая себя. То есть количество плохих комбинаций домов = (n-k)^(n-k). Количество хороших комбинаций домов можно наверное было тоже как-либо посчитать чисто теоретически, но у меня с первого раза не вышло. Посчитал брутфорсом для нескольких k начиная от единицы и увидел закономерность, что количество комбинаций хороших домов = k^(k-1). Вообще на закономерность можно было бы забить, просто сохранив полученные от значения для k=1..8, т.к. k никогда не бывает больше 8 по условиям задачи. Брутфорс примерно такой — k раз проходим циклам по хорошим домам, каждый раз помечая те, из которых можно попасть в первый дом.

У меня 0 взломов, у кого меньше?

:( submitted and got AC http://mirror.codeforces.com/contest/288/submission/3464296

No, elements 1,1 are allowed as well. It's a cycle from 1 to 1 of length 1 (non-zero).

First elements also can be 1 1

1,1 is a valid configuration :)

Was the solution of that person accepted? BTW same happened with me two time before no submission or hacks in last 2-3 minutes

({1,2},{1},{3,4,5},{3,4,5},{3,4,5})

2* 3^3 =54

По-моему, ты в точности описал то, как выглядит типичный Medium с topcoder'а, только забыл слово количество и решаться она обязательно должна при помощи дп :)

sorry, deleted.

I also couldn't submit D, and now I got accepted T_T

Same with my D. I first submitted a solution considering all possibilities with complexity O(k*k^k). When 2 mins were left, I realised that I could precalculate the values for k and then when I tried to submit in the last seconds, the servers did spoilers for me.

I coded a bruteforce and observed a possible greedy algorithm, hehe... not without sweating blood, though.

The first thing to notice is: the answer is always N(N+1) for a permutation of numbers 0..(N-1). Too bad that's not enough to solve the problem :D

So, try printing all possible permutations with answer N(N+1). Not good... although there is a nice pattern for even N, odd N is a problem.

If the permutation itself doesn't tell you anything, try something else... like the permutation xor-d with its indices! (I mean i^p[i] instead of just p[i]). Hmm... the lexicographically smallest permutation, xored with indices, gives a non-decreasing sequence of powers of 2 -1.

So what could be a good approach? Greedy, for example — we go from N-1 to 0, and maintain the largest allowed power of 2, and the numbers already used in the permutation. When trying to find i-th number, try xor-ing i with our largest power of 2 -1 and decreasing the power of 2, until the number which it gives is one that we could put in the permutation.

Miraculously, this works! :D

Everything that I say here is just what I observed during the contest, and I don’t know how to prove it (yet). Also, the pattern that I noted certainly isn’t the only one.

The maximum beauty is n(n + 1).

A possible answer for n = 2^k - 1 is {n, n - 1, ..., 1, 0}.

For n ≠ 2^k - 1:

Find maximum r = 2^k such that r ≤ n - 1 and construct the sequence v = {r - 1, r - 2, ..., 1, 0, r - 1, r - 2, ...} of length n (there will be only one zero in it).

For each i from r to n: remember v[0] and put i into v[0]. Write i - r as a sum of powers of two in ascending order. Then each element a of this sum means that you should put the remembered element a elements right behind the last touched element.

Example for n = 14:

(initial) 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 8)   8 6 5 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 9)   9 8 5 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 10)  10 8 9 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 11)  11 10 9 8 3 2 1 0 7 6 5 4 3 2 1 
(i = 12)  12 10 9 8 11 2 1 0 7 6 5 4 3 2 1 
(i = 13)  13 12 9 8 11 10 1 0 7 6 5 4 3 2 1 
(i = 14)  14 12 13 8 11 10 9 0 7 6 5 4 3 2 1 

Let’s see, for example, how’s transition from i = 13 to i = 14 done: i - r = 6 = 2 + 4, so 0th element is moved 2 positions to the right and 2nd element is moved 4 positions to the right.

My implementation: 3464172

Any installed plugins/addons? What?

Я пробовал, но не нашел закономерностей=)

Почему? Кол — во шагов == кол — во ребер в пути. Петля тоже как бы ребро :)

Почему? Увидели на доме табличку "1" — это уже действие. В терминах графа это тоже проход по ребру, только по петле.

p.s. Опередили

Контест мне понравился, но лучше бы как-нибудь иначе сформулировали условие по B. Или просто в примечаниях разобрали бы лёгкий пример 2 1.

После того, как не сошлось с ответом, нашёл, что во втором условии написано: "он точно не может дойти". В первом же слова "точно" нет, получается, разница в чём-то :)

В общем, упоролся и послал клар на это, а не на третье условие. К тому же багу словил.

По личному опыту: на олимпиадах по спортивному программированию, здравый смысл нужно выкинуть в окно.

I believe that the actual count (which is less than what you specified) could never overflow it. I used unsigned long long just in case though.

This value fits in unsigned long long and technically unsigned long long and long long are not different. Anyway it's like calculating answer modulo 2⁶⁴.

Let's estimate the number of paths containing the centroid (precisely, one of the centroids) of the tree (that's the vertex for which the subgraphs after deleting this vertex don't have more than n/2 vertices). Let's mark our centroid by v.

For each vertex w there are >= n/2 directed paths which start in w and contain v (that's because the size of the subtree containing w is less or equal n/2). It means that there are >= n*n/2 = (n^2)/2 directed paths containing the centroid, which gives us >= (n^2)/4 undirected paths, so >= n^2(n^2-1)/16 pairs of these paths.

You have to subtract this number from your expression. It means that the result does not exceed

R <= [n*(n-1)/2]^2 — n^2(n^2-1)/16 <= n^2(n^2-1)/4 — n^2(n^2-1)/16 = 3n^2(n^2-1)/16 < 2^63 for n<=80000.

It means the results fit in signed long long and these solutions must have passed :/

Edit: However, it would be funny if the behaviour of handling signed overflows was undefined ;)

That is very confusing!

there are some codes TLE with MS C++ and AC with GNU++. however, there are also some codes TLE with GNU c++ and AC with MS C++ .

so it's not easy to tell which compiler is better

I think so.

I THINK SO