593A - 2Char

For each letter will maintain the total length of words (cnt1_ci), which found it was alone, and for each pair of letters will maintain the total length of words that contains only them (cnt2_ci, cj).

For each row, count a number of different letters in it. If it is one, then add this letter to the length of the word. If two of them, then add to the pair of letters word`s length.

Now find a pair of letters that will be the answer. For a pair of letters c_i, c_j answer is cnt1_ci + cnt1_cj + cnt2_ci, cj. Among all these pairs find the maximum. This is the answer.

The overall complexity is O (total length of all strings + 26 * 26)

593B - Anton and Lines

Note that if a s line intersects with the j th in this band, and at x = x₁ i th line is higher, at x = x₂ above would be j th line. Sort by y coordinate at x = x₁ + eps, and x = x₂ - eps. Verify that the order of lines in both cases is the same. If there is a line that its index in the former case does not coincide with the second, output Yes. In another case, derive No. The only thing that can stop us is the intersection at the borders, as in this case we dont know the sorts order. Then add to our border x₁ small eps, and by x₂ subtract eps, and the sort order is set uniquely. The overall complexity is O(nlogn)

593C - Beautiful Function

One of the answers will be the amount of such expressions for each circle in the coordinate x and similarly coordinate y:

For a = 1, b = abs(t - i), it can be written as

Consider the a - b + abs(a - b):

if a ≤ b, то a - b + abs(a - b) = 0,

if a > b, то a - b + abs(a - b) = 2a - 2b

Now consider what means a > b:

1 > abs(t - i)

i > t - 1 and i < t + 1.

For integer i is possible only if i = t.

That is, this bracket is not nullified only if i = t.

Consider the 2a - 2b = 2 - 2 * abs(t - i) = 2. Then differs from the wanted position by no more than 1, but since all the radiuses are not less than 2, then this point belongs to the circle.

The overall complexity is O(n).

593D - Happy Tree Party

Consider the problem ignoring the second typed requests. We note that in the column where all the numbers on the edges of  >  1 maximum number of assignments to before x will turn into 0 is not exceeds 64. Indeed, if all the R_v = 2, the number of operations can be assessed as log₂(x). Hang the tree for some top and call it the root.

Learn how to solve the problem, provided that for every v R_v > 1 and no requests of the second type. For each vertex except the root, we have identified it as the ancestor of the neighbor closest to the root. Suppose we had a request of the first type from the top a to b vertices with original number x. We divide the road into two vertical parts, one of which is close to the root, while the other moves away. We find all the edges in this way. To do this, we calculate the depth of each node to the root of the distance. Now we will go up in parallel to the tree of the two peaks, until he met a total. If in the course of the recovery, we have been more than 64 edges, in the substitutions we get x = 0 and we can at the current step to stop the algorithm search. Thus, we make no more than O(log(x)) operations.

Let`s turn to the problem, where R_v > 0. We note that our previous solution in this case can work for O(n). Since the passage of the edge with R_v = 1 our value does not change. We reduce this problem to the above consideration. Compress the graph, that is, remove all single edges. To do this, run by dfs root and will keep the deepest edge on the path from the root to the top with R_v > 1.

Let us remember that we have had requests to reduce R_v. We maintain the closest ancestor of P_v c R_Pv > 1. We use the idea of compression paths. When answer to a request of the first type will be recalculated P_v. We introduce a recursive function F(v). Which returns the v, if R_v > 1, otherwise perform the assignment of P_v = F(P_v) and returns F(P_v). Each edge we will remove 1 times, so in total the call of all functions F(v) running O(n).

Final time is O(logx) on request of the first type and O(1) an average of request of the second type.

593E - Strange Calculation and Cats

Learn how to solve the problem for small t. We use standard dynamic dp_x, y, t = number of ways to get into the cell (x; y) at time t. Conversion is the sum of all valid ways to get into the cell (x; y) at time t — 1.

Note that this dp can be counted by means of the construction of the power matrix. Head of the transition matrix, T_i, j = 1, if we can get out of the cell i in a cell j. Suppose we had a vector G, where G_i equal to the number of ways to get into the cell i. Then a new vector G' by dt second G' = G * (T^dt).

So we learned to solve the problem without changes in O (log dt * S³), where dt — at a time, S — area.

Consider what happens when adding or removing a cat. When such requests varies transition matrix. Between these requests constant T, then we can construct a power matrix. Thus, at the moment of change is recalculated T, and between changes in the degree of erecting matrix. The decision is O (m * S³ log dt), m — number of requests

570А — Elections

We need to determine choice for each city. Then sum it for each candidate and determine the winner.

O(n * m)

Solutions

570B — Simple Game

Lets find which variant is interesting. For Andrew is no need a variant wherein |a - m| > 1 because we can increase probability of victory if we will be closer to m. Then we consider two variants, a = c - 1 and a = c + 1. Probability of victory will be c / n for first variant and (n - c + 1) / n for second.

We need to choose better variant, also we must keep in mind case of n = 1.

O(1)

Solutions

570C — Replacement

Lets find how replacements occur. If we have segment of points with length l,we need l - 1 operations and stop replacements for this segment. If we sum lenghts of all segments and its quantity then answer will be = total length of segments — quantity of segments. After change of one symbol length changes by 1.

Quantity of segments can be supported by array. Consider events of merging, dividing,creation and deletion of segments. For merging we need to find if both of neighbors(right and left) are points then merging occured and quantity of segments reduced by 1. Other cases can be cosidered similarly.

O(n + m)

Solutions

570D — Tree Requests

We need to write vertices in DFS order and store time of enter/exit of vertices in DFS. All vertices in subtree represent a segment. Now we can get all vertices in subtree v on height h as a segment, making two binary searches.

We can make a palindrome if quantity of uneven entries of each letter is less than 2.

This function can be counted for each prefix in bypass for each depth.

For saving the memory bit compression can be used considering that we need only parity and function is xor.

O(m * (log + 26) + n)

D had a offline solution too in O(n + m * (26 / 32)) time and O(n * 26 / 8) memory

Solutions

570E — Pig and Palindromes

We need palindrome paths. Palindrome is word which reads the same backward or forward. We can use it. Count the dynamic from coordinates of 2 cells, first and latest in palindrome.

From each state exists 4 transitions (combinations: first cell down/to the right and second cell up/to the left). We need only transitions on equal symbols for making a palindrome. Note that we need a pairs of cells on equal distance from start and end for each.

For saving memory we need to store two latest layers.

O(n³) — time and O(n²) — memory

Solutions

Greetings to the Codeforces community!

Regular Codeforces round #316 for participants from the second division will take place on August 13, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my first round on Codeforces. Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: The score distribution is standard, 500-1000-1500-2000-2500

Good luck!

UPD: Contest is finished. Thank you everyone!

Congratulations to the winners!

UPD Editorial