The intended solution doesn't require any theorem.

Let x, y, z be the number of vertices with degree 1, 2, 3, and let f(x, y, z) be the answer.

1) If y > 0, f(x, y, z) = f(x, y-1, z) * (the number of edges), because we can "insert" a vertex of degree 2 in the middle of an edge. 2) If y = 0, except for some small cases, f(x, y, z) = f(x-1, y+1, z-1) because the removal of one particular leaf will change a vertex of degree 3 to a vertex of degree 2.

Quick hints:

A: We can generate all divisorful numbers. If we consider only 3-smooth numbers and define divisorful numbers similarly, can you compute all such numbers? How about 5-smooth numbers? 7-smooth numbers? And so on.

H: First, for each i, compute the number of ways such that

• Start from (0, 0).

• Walk for i steps.

• After i steps, return to the original position for the first time.

H: Сначала нужно перейти от мат. ожидания к сумме по всем клеткам вероятности, что мы когда-либо окажемся в этой клетке. Теперь рассмотрим любую клетку на некотором пути. Пусть в последний раз на этом пути мы оказались в ней после k-го шага. Тогда нам нужно прибавить к ответу вероятность того, что мы придём в клетку (x, y) на k-м шагу и после этого больше не вернёмся в эту клетку за оставшиеся n - k шагов. Обозначим z_k — количество способов выйти из (0, 0), сделать k шагов и ни разу не вернуться в (0, 0). , где — количество способов попасть в (0, 0) за i шагов, стартовав из (0, 0). Таким образом, ответ это , где q_xyk — количество способов попасть в (x, y) из (0, 0) за k шагов. Если поменять порядок суммирования, то q_xyk просуммируется к 4^k. Таким образом, ответ это просто .

а можно доказательство этого решения

Другое решение — поменяем координаты точек на (x[i]+y[i],y[i]-x[i]). В таких координатах манхеттенское расстояние равно максимуму модулей разностей координат.

Переберем ответ двоичным поиском и будем явно строить граф.

Две вершины будут связаны, если модуль разницы хотя бы по одной из координат не меньше текущего ответа.

Посмотрим все точки в порядке сортировки по первой новой координате. Первая в порядке сортировки точка будет соединена с каким-то суффиксом такого массива, последняя — с каким-то префиксом. Очевидно, что других важных ребер нет. Аналогично проведем нужные ребра по второй координате.

Получившийся граф проверим на связность и в результате куда-то сдвинем границу бинпоиска.

When N is odd, put N points around a circle, and choose all isosceles triangles.

When N is even,

• Put N-1 points around a circle, and choose all isosceles triangles.

• Add (the remaining point) — (i) — ((i+1)%N) for each 0 <= i < N.

• Add (the remaining point) — (i) — ((i+2)%N) for each 0 <= i < N.

• Remove extra triangles.

We should find proper coefficients but basically this is the idea of the answer.

Сгенерить все разности, и понять, куда мы можем сдвинуться за четное число ходов — это все возможные суммы этих разностей. Можно доказать, что если мы хотим попасть в что-то в пределах 10^4, то можно за эти пределы не выходить, поэтому bfs работает за 10⁴ * 10⁴

My team had the same problem. We mistakenly believed that the line of "e" can not get the string "egg". After fixing, we passed the test. Perhaps a similar case in the test 3. P.S. Sorry for my bad english

уже все в порядке, но contest is over

Few corner cases. If we have only one color, the answer is -1. Another corner case is the second sample — we have some cards of the same color and a card of some other color between them. The answer is 0 in this case.

Now let's move to the general approach.

Let's decrease each a[i] by one. Now we have to find the amount of such numbers k, the a[i]/k == a[j]/k if and only if c[i] == c[j].

The key observation is that for fixed number N there are only different values of N/i for all possible values of i.

Based on this we can build a set of constraints in form of

1) Segment [l; r] may be the answer (we get this from a pair of cards with the same color)

2) Segment [l; r] can not in be the answer (we get this from a pair of cards with different colors)

To find the answer we should find the total length of the segments, that are covered by all of the constraints of the first type and are not covered by any of the segments of the second type. This can be done using some kind of a sweeping line.

Code

By the way, you asked the question in the Russian thread

Division 1

Division 2

We only need some edges. For every point we can reach this point from maximum 4 points(point J which has smallest Y, X[I] = X[J] and Y[J] > Y[I] and have direction 'D'.also for all other 3 direction). So we only have maximum 4 * N edges and now we can use simple dijkstra algorithm to get switch time of every robot. solution author LashaBukhnikashvili

If someone is still interested in solution, it's dp[i][j] where i and j are the suffixes of the given permutations. If s1(i) != s2(j) then dp[i][j] = dp[i + 1][j] + dp[i][j + 1]. If s1(i) = s2(j) so let len be the length of the longest common prefix of these suffixes. Then we are in danger of counting some array twice untill one of our indices(i or j) has reached position i + len + 1. So let's say i will move to i + len + 1 before j will move to j + len + 1. Let's try every k so that we will go to the state dp[i + len + 1][len + k], k <= len. We need to count number of arrays that can be obtained from substring (i ... i + len) of the first permutation and from substring (j ... j + k — 1) of the second permutation. We will avoid double counting if we will not take number from the second permutation if we took less numbers from the first permutation. So it's equivalent to the number of bracket sequences with len opening brackets and k closing brackets. It can be precomputed by simple dp or using formula described in this comment http://codeforces.net/blog/entry/23266?#comment-276645. Then we have do the same for the index j. There are only O(n) such states.

Pleade read about Prufer codes (that's a bit overkill, but a very nice one).