We were waiting several weeks to setting this contest and hope the problem was good enough.
Events
There was a difficulty with 805E - Раскраска мороженого/804C - Раскраска мороженого. A little bug in the checker fortunately yields accepting an incorrect solution of only one person during the contest. I should apologize all of you because of this.
For this sentence, Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.
You can find the meaning of "connected subgraph" with connected and subgraph, thus it can be empty as it is more logical. How ever, I should apologize all of the participants because of weak sample tests in the statement.
I will write the full editorial in the few next days, now some hints and short solutions exist here.
Hints
805A - Не NP
hint1Almost half of numbers are divisible by two.
805B - 3-палиндром
hint1For the string shouldn't be any i ≤ n - 2, si = si + 2. Make some examples of little sizes.
805C - Найти Амира / 804A - Найти Амира
hint1Find minimum weighted edges.
hint2There is some edges with weight 0, try to connect them in a carefully way.
805D - Минимальное число шагов / 804B - Минимальное число шагов
hint1The last situation is some 'a' characters after some 'b' ones.
hint2The last situation is unique.
hint3The number of steps is also unique.
hint4Each 'b' character makes a number of 'b' characters in the last situation according to the number of 'a' characters before it.
805E - Раскраска мороженого / 804C - Раскраска мороженого
hint1We want to color the ice creams in a way that all of ice creams in a vertex would be different with this condition that if two vertices u and v have ice cream i, then all of vertices in the unique path of u and v would have it.
hint2Let's have a trivial lower-bound for the answer.
answerThe trivial lower-bound should be maximum size of vertices' sets.
hint3You can prove that by induction on leaves of the tree. And code it how you proved it.
805F - Матожидание диаметра дерева / 804D - Матожидание диаметра дерева
hint1Let's solve the problem for just two tree.
Trivail solutiondt is diameter of t-th tree and fi is the maximum path starting from vertex i, for all valid i and j, assume that the edge is between them and find the diameter with max(fi + fj + 1, max(d1, d2)).
consider this trivial solution and try to improve it to .
hint2 Actuallyseems SQRT.
How?For every new query, try to do it with the complexity of , which szi means size of the components of i-th vertex. Prove its complexity is .
804E - Та же перестановка
hint1You can prove, we need even number of swaps to reach the same permutation. So and the answer for 4·k + 3 and 4·k + 4 is -1.
hint2The solution almost is constructive.
Try to solve it for n = 4And then solve n = 8 by n = 4.
hint3Let's partition n = 4·k numbers to classes, each class contains a 4 consecutive numbers. And when n = 4·k + 1 there is a class with 5 consecutive numbers.
804F - Фальшивые слитки
hint1The problem consists two parts, the first part is to find mni and mxi, the minimum and the maximum score i-th vertex may get after the score distribution. The second part is to finding the answer and all your need to solve this part is those two arrays. It is trivial mni is number of real bullion of golds in i-th vertex.
hint2Let's find the scores for two vertices u and v, u have a directed edge to v.
hint3If we have this directed walk {w1, w2, ..., wk}, you should affect v1 on vk how I said in the previous hint with .
What about strogly connected components. hint4SCC of the tournament yields a Hamiltonian path of strongly connected components( if we consider each component a vertex ). The problem decreased to solve this path. we can solve the path with the complexity of sum of vertices' sizes.
hint5Now, for every vertex we have minimum and maximum score it may get. For B known vertices, to check if they can be the wanted set, we can assume their score be maximum possible and the other scores be minimum possible. If they were top, then they can be a sample of the wanted set.
hint6Consider a sorted sequence of combination of two array mn and mx.
For every vertex, consider the number of ways it(with its maximum score) can be the minimum score of the set of B vertices.
Solutions
To DO...