150E - Freezing with Style

1. If there exists a path with the median  ≥ k, for some k, then there exists a path with the median  ≥ q, for each q ≤ k. That means we can use binary search to calculate the answer. So now the task is: is there any path with the median greater or equal to Mid ?

2. We will calc the edge as  + 1 if it's wight  ≥ Mid, or as  - 1 in other case. Now we only need to check if there exists a path with legal length and the sum greater than or equal to zero.

3. Let's denote some node V as a root.

4. All paths can be divided into two types: that contains v, and that do not. Now we are to process all first-type paths and run the algorithm on all subtrees. That is so-called divide-and-conquer strategy.

5. We can trivially show that it is always possible to choose such vertex v that all it's subtrees will have size less than or equal to the size of the whole tree. That means that each node will be proccessed in LogN trees max.

6. So, if we solve the task for one level of recursion in O(F(N)), we'll solve it in time O(F(N) * log²(N)) on the whole.

7. First, lets get O(N * Log(N)). For each node we shall calc it's deepness, cost of the path to the root ans the first edge (the number of the root's subtree). It will be better now to use 2 and 0 as the edges costs, instead of -1 and 1. Now we shall process root's subtrees one by one. For each node we want to know if there exists a node u in any other subtree such that the

   Unable to parse markup [type=CF_TEX]

   and cost[v] - deep[v] + cost[u] - deep[u] ≥ 0. To do that we need to know the maximum of the function (cost[u] - deep[u]) with the deep values between max(0, L - deep[v]) and R - deep[v] inclusive. To achieve O(N * log(N)) you need only to use segment tree.

8. To achieve an AC contestants were to write all code optimally, or to think of one more idea. It is possible to have O(N) on one level of recursion and O(N * log²(N)) in total if you sort roots subtrees in non-decreasing order and use any structure that can answer getmax query on all segments of length (R - L + 1) and all prefixes and suffixes.

Best of luck to you in upsolving this problem!

150D - Mission Impassable

In this problem you have to use dynamic programming. For our convenience we will calulate three type of values:

Best[l][r] — best result player can achieve on the segment [l, r].

Full[l][r] — best result player can achieve on the segment from [l, r] if he fully destroys it.

T[l][r][Len] — best result player can achieve on the segment from [l, r] and remain the palindrome of length len and only it.

Now solution:

1. Full[l][r]. Let's look which move will be the last. This will be removing the palindrome of length len and c[len] ≥ 0. What is the best result we can achieve? c[len] + T[l][r][len].

2. Best[l][r]. Either we will destroy all subtring from l to r, either there exists a letter which we did not touch. That means that all our moves lies fully to the left or fully to the rigth to that position. So Best[l][r] = Full[l][r] or Best[l][r] = Best[l][m] + Best[m + 1][r] for some m, l ≤ m < r.

3. T[l][r][len]. len = 0, len = 1 — two special cases, which is easy to solve without any dynamic. In other case, let's take a look on the left-most position. It either will lie in the result string or not. If not, then let's find the first position which does. Denote it as m (l < m ≤ r). Everything what lies to the left need to be fully deleted. So the answer is Full[l][m - 1] + T[m][r][len] (for l < m ≤ r). Similarly, for the right-most letters. If it does not lies in the result string we remove everything to the right and our result is T[l][m][len] + Full[m + 1][r] (for l ≤ m < r). The last option: both left-most and rigth-most letters lies in the result string. It is possible only if s[l] = s[r]. So our result is T[l + 1][r - 1][len - 2] (only if s[l] =  = s[r]).

150C - Smart Cheater

1. First lets use the linearity of expected value and solve task independently for each passanger.

2. For each path segment (route between neighboring stations) we calculate expected value of profit in case we do not sell a ticket for this segment. In case we sell it the expectation of profit is 0.

3. Now we only need to find the subsegment of segment [a, b] of maximal sum for each passanger.

4. That's easy to do by the segment tree, we only need to calc four values for each node:

best — the maximal sum of elements on some subsegment

max_left — the maximal sum on prefix

max_right — the maximal sum on suffix

sum — the sum of all elements

150B - Quantity of Strings

We can offer you two solitions:

1. You can build a graph with positions in sting as a nodes and equality in any substring of length k as edges. Lets denote e the number of components in the graph. The answer is m^e.

2. Analyze four cases:

   • k = 1 or к > n, the answer is mⁿ.
   • k = n, the answer is m^{(n + 1) / 2}.
   • k mod 2 = 1, any string like abababab... is ok, so the answer is m².
   • k mod 2 = 0, all symbols coincide and the answer is m.

150A - Win or Freeze

• if Q is prime or Q = 1 than it's victory.

• We loose if: Q = p * q or Q = p², where p and q are prime.

• It is quite obvious that it is always possible to move in bad position in any other case. That means all other numbers grants us the victory.

We only have to check if Q has a divisor of the loose type. We can easily do it in O(sqrt(Q)) time.

151B - Phone Numbers

In this task you were to implement the described selection of the maximum elements.

151A - Soft Drinking

Soda will be enough for gas = (K * L) / (N * l) toasts.

Limes will last for laim = (C * D) / N toasts.

Salt is enough for sol = P / (p * N) toasts.

Total result: res = min(gas, laim, sol).