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://codeforces.net/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

I'am sorry to make mistake on this when I summited it at 7 minute.But I soon found that lots of people got hackings.So I realized it and put it right within 2 minutes,luckily.

This rating is quite difficult to keep.

this is great contest

Excellent explanation. Here is a link to wiki for those who interested: http://en.wikipedia.org/wiki/Cayley%27s_formula

And (n-k)^{n-k} for remaining houses is because its irrelevant what kind of mapping do you choose as long as it is surjective.

(The matrix-like scheme is irrelevant; Consider we have N=n*m numbers in a array v[0..N-1] as input).

First of all, please notice that when you add or subtract the value d from a value v[i], its remainder by d is not changed (i.e., (v[i] +/- d) mod d = v[i] mod d ).

Since you can't change the value of (v[i] mod d) by applying any number of moves to v[i], there is a solution if and only if the value of (v[i] mod d) is the same for all i.

So, if there isn't a solution, print "-1". Otherwise, the problem is kinda classical: you'll change all the elements to the median of the values given in the input. So, sort v and sum |v[i]-v[N/2]|/d for all i.

It actually means that if he starts from any house numbered 1 to k, inclusive, then there will be a path from the house he started to house number 1. He must not get back to the house he started walking from but there must be a path from any house with index 1 to k to house 1.

No , it only means he can reach house number 1.

I still don't get it. What does "Can" mean here? There must be a path from every house between 1 and k inclusive to the first house? Or there "can" be such a path?

for each array index such i you should calculate the number a that a + i = ( 2 ^ k )-1 and this number hasn't been used yet in the permutation C++ code:3461375 There is a simple way for the implementation, calculate powers of 2 and check it for the array index elements, from n to 0

This is my solution. It differs from solutions of other participants. Lets denote z1[v,is,ab,cd] — dp for subtree of vertex v. is equal to 1 if vertex v is already on some path and equal to 0 otherwise. ab is equal to 1 if we need to create path ab in subtree of v. cd is similar. To calculate this dp we need to calculate another dp z2[v,idx,is,ab,cd,cnt] (cnt in range 0,2). z2 means that we considering the idxth son of vertex v, cnt is the number of sons to whom we can prolong some path. This is my AC 3465665 submission.

Never use google translate.

Разборамана будет пожже. Много делов.

I'll post the rest of the editorial and translation a bit later. Sorry for delay.