A. Дана строка...
Переберём все подстроки, начиная с самых длинных, и для каждой посчитаем, сколько раз она встречается. Сложность — O(L4) с маленькой константой.
B. Вечеринка
Ясно, что хотя бы один человек (тот, у кого меньше всех знакомых) должен уйти. Докажем, что должны уйти хотя бы двое. Действительно, пусть ушел только один человек, и у него d знакомых. Тогда у остальных до его ухода было больше d знакомых, а после его ухода стало меньше, чем d + 1, то есть не больше d. Значит, его уход повлиял на количество знакомых у каждого из оставшихся, то есть он знаком со всеми: d = N - 1. Но у него меньше всех знакомых — противоречие.
Итак, ответ не больше N - 2. Покажем, что N - 2 человека могли остаться (если, конечно, N > 1). Организуем граф знакомств следующим образом: возьмем полный граф на N вершинах и удалим одно ребро. Тогда степени двух вершин равны N - 2, а степени остальных N - 1. После удаления первых двух вершин остается полный граф на N - 2 вершинах, и все степени равны N - 3, поэтому больше никто не уйдет.
C. Апельсины и яблоки
Отсортируем ящики в порядке возрастания числа апельсинов. Посчитаем общее число яблок в ящиках с нечетными и четными номерами. Если в ящиках с нечетными номерами яблок не меньше половины, то выберем их (их ровно N). Если же в ящиках с четными номерами яблок не меньше половины, то возьмем их и добавим к ним самый последний ящик (в котором больше всего апельсинов). Нетрудно видеть, что в обоих случаях требуемые условия выполнены.
D. Четырёхугольник
Пусть ABCD — искомый четырёхугольник, а K, L и M — середины равных сторон AB, BC и CD соответственно. Пусть M' — точка, симметричная M относительно L. Тогда BM' = CM = CL = BL = BK, то есть B — центр описанной окружности треугольника KLM'.
![](/predownloaded/b7/2d/b72d164e3aef2642dd05b2477ac0395cc5751945.png)
Зная B, можно восстановить весь четырёхугольник с помощью симметрий относительно точек K, L и M, и затем проверить, выполнены ли для него условия строгой выпуклости и равенства сторон.
Заметим, что мы не знаем, какая из данных точек является точкой L, поэтому нужно проверить все 3 варианта.
E. Дерево
Лемма. В одном из оптимальных решений отсутствуют простые пути длины 3.
Доказательство. Из такого пути можно выкинуть среднее ребро. Тогда компонента связности распадётся на две компоненты размеров a и b, причём a ≥ 2, b ≥ 2, поэтому ab ≥ a + b.
Подвесим данное дерево за любую вершину. Будем рекурсивно вычислять следующие величины: hv — решение задачи для поддерева с корнем v и fv — произведение hu по всем сыновьям v. Для листов hv = fv = 1.
Покажем, как вычислить hv, зная решение для всех поддеревьев v. Рассмотрим компоненту связности v в оптимальном решении. Из леммы следует, что она имеет один из следующих видов:
1. Единственная вершина v.
2. Вершина v и несколько её сыновей.
3. Вершина v, один её сын — w и несколько сыновей w.
В первом случае результат игры равен fv.
Во втором случае он равен Πfi · Πhj · k = Π(fi / hi) · fv · k, где i пробегает сыновей, входящих в компоненту, j — остальных сыновей, а k есть размер компоненты. Поскольку мы хотим максимизировать это выражение, нас интересуют сыновья с как можно большим значением fi / hi. Поэтому наилучший результат во втором случае равен максимуму по s Πi ≤ s (fi / hi) · fv · (s + 1), где считается, что сыновья отсортированы по убыванию fi / hi.
В третьем случае для каждого сына w можно провести аналогичные рассуждения. Наилучший результат будет равен максимуму по w и s выражения fv · (fw / hw) · Πi ≤ s (fi / hi) · (s + 2); отметим, что сыновья w уже были отсортированы на предыдущем шаге рекурсии.
Таким образом, количество операций, необходимых для определения fv, пропорционально суммарному количеству сыновей и внуков v, что не превосходит n. Следовательно, сложность алгоритма (не учитывая операции с длинными числами) — O(n2).
P. S. Приношу извинения за формулы, похоже рендерер латеха сломался. Добавления и замечания приветствуются.
В задаче D одну из вершин можно также найти, если отразить серединный перпендикуляр к KL относительно точки L и пересечь с серединным перпендикуляром к LM. Это не намного проще, так что здесь скорее дело вкуса.
Hope that the lack of comments indicates that everything is clear rather than the opposite :)
(BTW, you posted it under the russian language)
O(N) can easily be achieved with suffix trees.
I would be very grateful if someone could clear this up to me...
> whatever the configuration, there will be no one with exactly N friends, so everyone will have to leave...
When a person leaves, the number of friends for other people changes.
Then how can we get someone to have N friends in the incomplete graph so that person remains in the end? As I understood it, the number of friends for other people will be strictly decreasing as time goes on, so if someone is to have N friends at some point, he must have had at least N friends previously... Either that or I really can't understand the problem...
I think I should be able to understand it best if you could show me an example for a small N...
1--2--3
At the first step no one gets eliminated, since there are no vertices of degree 0.
At the second step the vertices of degree 1 get eliminated and only vertex 2 stays. Now 2 has degree 0.
At the third step no one gets eliminated, since there are no vertices of degree 2.
Thank you for your time and patience.
На самом деле, во время вычислений всех этих произведений каждая вершина будет просмотрена только 2 раза, у отца и деда. Поэтому без учета длинных операций сложность равна O(N). Но cами числа будут порядка 3N / 3, то есть их длина равна O(N). И получается, что алгоритм имеет сложность O(N3). Но скрытая константа здесь очень маленькая.
Можно даже получить более точную формулу для асимптотики. Длина чисел при N ≤ 700, не превосходит 700 lg(3) / 3 ≤ 112, а так как обычно основание в длинной арифметике равно 10000, то даже в 4 раза меньше, то есть не больше 30. Итого, сложность равна O(N(L log N + L2)), где N ≤ 700 и L ≤ 30, что вполне приемлемо.
Can someone explain why the editorial solution to problem C is correct? I've thought about it for a while and still cannot get why selecting all the odd ones, or all the even ones guarantees that it will be correct.
Thanks.
Suppose 0 ≤ x1 ≤ x2 ≤ x2N - 1 are numbers of oranges. Sum the inequalities x1 ≥ 0, x3 ≥ x2, ..., x2N - 1 ≥ x2N - 2. We get x1 + x3 + ... + x2N - 1 ≥ x2 + x4 + ... + x2N - 2. It means that the left part of the inequality (boxes 1,3, …, 2N-1) contains at least half of all oranges.
Similarly, sum the inequalities x2 ≥ x1, x4 ≥ x3, ..., x2N - 2 ≥ x2N - 3, x2N - 1 ≥ 0. We get x2 + x4 + ... x2N - 2 + x2N - 1 ≥ x1 + x3 + ... + x2N - 3. It means that the left part of the inequality (boxes 2,4, …, 2N-2, 2N-1) contains at least half of all oranges.
Now the first subset 1,3, …, 2N-1 contains all odd boxes, and the second one 2,4, …, 2N-2, 2N-1 contains all even boxes. It means that one of them contains at least half of all apples and we may choose it to solve the task.
I am not able to get the logic as why should either of the first subset 1,3,...,2N-1 or second one 2,4,2N-2,2N-1 should contain atleast half of the apples.
Can you please explain ?
If the sum of two numbers is greater than or equal to s, then at least one of them is greater than or equal to
.
i do not understand the explanation for problem E. please can any one give an easier explanation.
For problem E, an O(n) greedy algorithm is possible (ignoring big numbers). See my code for detail 25487437.
could you explain more ?
Yes. After DFS in a subtree completes, the solution will already make optimal cut in the subtree, and returns a reduced shape that still matter in later decision. Such shape is identified by a integer:
When recursion on all children finished, we keep track of all case numbers for children.
It won't be hard to prove that you can make globally optimal edge-cut decision by just looking at c0, cp, cn, and reduce the subtree into one equivalent case number to return.
what do you mean by [[]] '[' show what ?
each '[' and ']' pair is a node. child nodes are inside parent nodes.
alright ; but why this greedy algorithm works ; i mean why the best possible answer depends on the best answer of its child's ; consider now you are on vertex v and u is child of v ; maybe the best answer of u returns 1-1-fork-k ; but in the best answer of vertex v we have to use u as a leaf ;
That's why u-1-fork-k is one of the reduced cases.
When parent v finishes DFS and reduce its subtree, it can cut (1-fork-k) off, and return a two chain (v-u).
And the already cut part will contribute to answer immediately.
In one of optimal solutions there are no simple paths of length 3 ..
what it mean ?
can anyone please explain me 2nd and 3rd case formula ?
A simple path is a path in a graph which does not have repeating vertices
"Then all other people had more than d friends before he left, and after that they had less than d + 1 friends, i.e. not more than d."
Why couldnt they have had d+3 friends say before and consequently d+2 afterwards?
Because then they will leave at step d+2, and we assume only one person left.
Thanks.
"correspondingly. Let M' be the point symmetric to M with respect to L". Do you still have the picture describing this? Im finding the tutorial hard to follow.
Found it on archive.org: https://web.archive.org/web/20140715212706if_/http://img685.imageshack.us/img685/8097/task.png