I used a greedy algorithm that moves the numbers in increasing order one after another to the correct places. You can always move the number either to the left or to the right and select the direction that minimizes the number of swaps.

For example, if the array is [6, 4, 1, 5, 2, 3], we first move number 1. If we move it to the left, we need 2 swaps, and if we move it to the right, we need 3 swaps. So we move it to the left and the array becomes [1, 6, 4, 5, 2, 3]. After this, we move number 2 etc.

Можно чуть поподробнее: вот мы сдвинули min элемент в самое лево. И что дальше?

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

Ключевое наблюдение — если мы выставили n+m минимальных элементов в префикс и суффикс, то позиция минимального из еще не выставленных элементов относительно других еще не выставленных элементов не зависит от значений n и m (только от начальной перестановки и значения n+m). Поэтому выбор более близкого края не влияет ни на что в дальнейшем.

Вне зависимости от остальных сдвигов 1 будет на одном из краёв. Чтобы передвинуть её на левый край, её в любом случае придётся обменять со всеми теми, которые больше неё и левее (опять, вне зависимости от всех остальных сдвигов и их порядка: если есть кто-то больше и левее, с ним необходимо будет рано или поздно поменяться), т.е. просто больше, т.к. мы двигаем именно 1. Итак, за меньшее число обменов не получится, а ровно за такое это делается тривиально.

Я решал эту задачу на опенкапе лет пять назад.

Я ее видел на одном из Всесибов.

Я ее решал на одном из опенкапов. Так было что-то про тараканов, которые очередями пересекают кухню.

Первые 3 — бояны. Вероятно, я бы мог такое сказать и о четвертой, если бы на контестах читал все задачи))

Первая была где-то на кодчефе, была на снарке в прошлом году, да и вообще боян.

Вторая была на каком-то из regionals.

Третья была на ТСO, на Opencup и на Challenge 24.

А вот я не искал легких путей и написал ее обходом лабиринта по правилу правой руки...

Ага... Как минимум я её давал на очный тур всесиба несколько лет назад. Только там все координаты были до 10^9, чтобы не было соблазна что-то изобрести =)

Ну и до кучи, в евклидой метрике и чуть-чуть другой формулировке она была на школьних летних сборах России 2010 года.

Решил D примерно как ты сказал, но неправильно. В результате написал там ещё и динамику по поддеревьям, она-то и прошла :)

Actually, you pulled a jodik. In March 2012 on Slovak OI nationals (practical day: 2 problems, 15 points each, IOI scoring, full feedback, last submission counts), he resubmitted one problem's solution on another problem (for which he had full score), and then again on the correct one, where he found out that it's still a wrong solution, giving him 0 points total :D

Fortunately, he managed to convince the organizers to accept his earlier solution, so he did get the points in the end.

Dynamic programming in subtrees — for every node of trie, for every 0 ≤ n ≤ N calculate maximum number of nodes if subtree is stored on n servers.

My solution:

• construct the original trie; for each vertex, remember how many strings ended exactly in it (e[v]) and how many ended in its subtree (s[v]); it's clear that we can put min(s[v],N) strings (as many as possible) from its subtree into distinct servers, so each vertex appears this many times and the first part of the answer is the sum of min(s[v],N) over all vertices (including the one corresponding to the empty prefix)

• it's also clear that we can only achieve this many vertices in total if these bounds are exactly satisfied for each vertex, so:

  • if a node has s[v] ≥ N and all its sons have , the strings ending in each son's subtree must be put into distinct servers and the strings ending in the subtree of v must span over all N servers
  • if a node has s[v] ≥ N and at least 1 of its sons has , the strings ending in each son's subtree must be put into distinct servers

• in the second case, if the strings in some son's subtree span over all servers, then the ones in the parent's subtree also do; also, if the strings in a parent's subtree are all in distinct servers, then the strings in any son's subtree also are, so the conditions for the remaining vertices are automatically satisfied; this set of conditions is also necessary

• feel free to pre-calculate all factorials, their modular inverses and binomial coefficients up to 5000x5000

• there are ways to put m < N strings into m servers out of N — we choose the servers with one string and then the order of placing the strings; in the second type of vertices, m = s[v]

• let P(m, n) be the number of ways of putting m strings (from a specific subtree) into n servers (m ≥ N ≥ n) in such a way that there's at least 1 string in each server (the strings span over all n servers), and P₀(m, n) the number of ways when we allow some server to not contain any of these strings; then , because we just subtract the choices that end up with exactly n - k > 0 servers empty

• we can calculate P₀ by realizing that each of e[v] strings can go into any server and each son of v (the subtree's root) must satisfy the condition above, and these rules are independent, so P₀ is the product of e[v]ⁿ and over all sons of v

• using modular exponentiation, we can calculate P₀(m, n) for any subtree in time; then, we can DP all P(m, n) up to P(m, N) (which is the actual number of ways that satisfy the basic condition for v) in time; over all vertices, we get worst-case , where L is the total length of strings in the input

• the second part of the answer is just the product of ways to satify the conditions for all vertices, for which they need to be satisfied (P(m, N) or )

I agree. C was a beautiful problem. Mincut -> Maxflow is a common theme in programming contests, but it's so rare to see it go the other way around.

Last year, I got mine at the end of August. If you hope to get it soon, you'll probably be disappointed...

In my case, it was shipped around 6 to 7 months later.