D: Сначала заметим, что вершина U является сыном V если время_входа[V] <= время_входа[U] <= время_выхода[V]. Если вершины на высоте H отсортированы по времени входа, то границы можно найти бинарным поиском.

Начинаем расширять палиндром из центра.

dp[сколько букв набрали в обе стороны относительное центра][номер клетки на идущей влево-вверх][номер клетки на идущей вправо-вниз]. для каждой пары клеток есть условия x1 + y1 = x2 + y2, из этого у нас O(n^3) состояний.

Переходов у нас 4, идем по равным клеткам из текущей пары по всем возможным направлениям.

Ответ лежит в dp[(n + m) / 2][(1;1)][(n;m)]

thanks for Editorial :)))

Some of my thoughts: we can firstly compute the depth of each vertex and use a list to record the order of vertices in each depth. Let's consider the mentioned example (see the problem). the order of vertices in each depth is:
Depth 1: 1
Depth 2: 2, 3, 4
Depth 3: 5, 6
This process can help us quickly find the vertices in depth h for the required vertex v in the following. Going on, after that, we use DFS to record the in-time and out-time of each vertex. For the given example, we have the DFS order as follows:
DFS order: 1, 2, 2, 3, 5, 5, 6, 6, 3, 4, 4, 1
This can be addressed by applying the following pseudo-code:
time = 1;
DFS(vertex u)
    in[u] = time ++;
    for each son v
        DFS(v)
    out[u] = time++;
The above-mentioned two steps can be considered as a pre-processing operation. Then, for each query, denoted by <v, h>, we find the answer as follows.
Case 1: if h is no more than the depth of v, return "Yes".
Case 2: if v has no posterity that locates in depth h, then return "Yes".
Case 3: Otherwise, find the required vertices in depth h, and judge "Yes" or "No".
It can be said that, Case 1 is easy to solve. Here, Case 2 and Case 3 will utilize binary search (BS) to find the answer. Clearly, we will use BS to find the most left vertex (posterity) and the most right vertex (posterity) in the Depth-list of depth h for the vertex v. The BS exploits the in-time and out-time to find the most left vertex and the most right vertex. For example, if we want to find the most left vertex in depth h for the vertex v, we use the following pseudo-code:
l = 0, r = Depth[h].size() -1, ans_left = -1;
while( l <= r )
    m = (l + r) >> 1;
    if vertex Depth[h][m] is posterity of v
        ans_left = m, r = m -1;
    else if the ancestor of Depth[h][m] in depth "dep[v]" is in the left of v
        l = m + 1;
    else
        r = m -1;
Here, we will utilize the in-time and out-time of a vertex to judge that: whether a vertex A is the ancestor of a vertex B, or the left/right one of the ancestor of B in the Depth-list.
An accepted source code: 12519227

Let's assume f(x1, y1, x2, y2) be the function which gives the number of ways of going from point (x1, y1) to (x2, y2).

Now, the basic recurrence without memoization can be seen as :

f(x1, y1, x2, y2) :
  if S[x1][y1] != S[x2][y2] : return 0
  if x1 > x2 or y1 > y2 : return 0

  // include the base case when have two neighbouring cells or single cell
  // if neighbouring cells have same value return 1
  // else return 0

  ans = 0
  ans = ans + f(x1 + 1, y1, x2 - 1, y2)
  ans = ans + f(x1, y1 + 1, x2 - 1, y2)
  ans = ans + f(x1 + 1, y1, x2, y2 - 1)
  ans = ans + f(x1, y1 + 1, x2, y2 - 1)
  return ans

Also, one argument in the recursive function is dependent on other 3, if we know x1, y1 and x2, we could compute y2 because the points are such that the manhattan distance beetween (1, 1), (x1, y1) and (n, n) and (x2, y2) are same.

So, we could have three arguments to the recurrence. And as there's no loop inside, time complexity of the solution after memoization would be O(n^3). But, space complexity will also be O(n^3). To make the solution run in required space (256MB), observe the fact that the current layer (equidistant set of points from (0, 0)) is only dependent on next set of layers (points with distance one more) we could write a bottom up dp with O(n^2) space. Storing just last one calculated layer everytime.

I wrote top-down dp with memoization, got Memory Limit Exceeded, couldn't code bottom-up dp properly in time! :'(

I solved it with the same complexity but using binary indexed tree

But this overkilles the problem alot in my opinion

This solution is the sane as before but without logn

I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578

At first I was trying to come up with a solution similar to the editorial, but then I realised that a change in F is only influenced by the neighbours.

Anyways, here is my solution if anybody needs more help: 12512037

Great, thanks, so simple :) AC 12522984

Consider the simplest case: The string, of length L, is formed by all dots. Clearly f(s) = L - 1.

Imagine there k strings of consecutive dots of length L₁, L₂, ... L_k, separated by non-dot characters, the answer is just taking the sum of respective reductions, namely,

Let's see how we can perform updates in constant time.

Case 1: A segment's boundary becomes a non dot character. Number of dots reduced by 1, and number of segments is reduced by at most 1, depending on whether the segment is of length 1 or not. So the answer is reduced by at most 1.

Case 2: A segment's boundary is extended by 1, but not merging other segments. Number of dots is increased by 1, number of segments unchanged. So the answer is increased exactly by 1.

Case 3: A new segment is added (of length 1). This is the same as Case 2.

Case 4: One segment is broken by two non empty segments (otherwise, it's just case 1). In this case, number of dots is reduced by 1, the number of segment is increase by 1. So the answer is reduced by 2.

Case 5: Two non empty segments are merged. Number of dots is increased by 1, and the number of segments is reduced by 1. So the answer is increased by 2.

So you need to check neighbors of the changing position to see which case the operation falls into and update the answer in constant time accordingly.

Each substitution on s[xi] (ci' -> ci) will only effect s[xi]'s two neighbors(s[xi-1] and s[xi+1], if it has). Only need to recalculate the value on (s[xi-1], s[xi], s[xi+1]).

Your solution O(m * log * 26 + n). It is close to time limit.

My solution took 1996 ms. I'm running in the house yelling "Damn!".

Так получилось из-за того, что количество вершин не являющихся корнем n — 1 и при общем количестве вершин n = 1, вторая строка содержит 0 чисел по условию.

Извиняюсь если это было не понятно.

Из условий.

Выведите одно целое число — такое значение a, чтобы вероятность победы Андрея была максимальной. Если таких значений несколько, выведите минимальное из них.

А ещё бы понять в чём разница цикла for и метода forEach у ArrayList?

http://codeforces.com/contest/570/submission/12536065 (RE48)

http://codeforces.com/contest/570/submission/12536271 (AC)

Заглядывая внутрь интерфейса Iterable видим:

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

Казалось бы в чём разница:

edges[v].forEach(v2 -> dfs(v2, lvl + 1));

и

        for (int v2 : edges[v]) {
            dfs(v2, lvl + 1);
        }

If A is greater than the number of M, we are winning on any value from A to N.

Хорошо.

Where is the input string?

Yes

F(...) = 2 (... -> .. -> .)

F(.a.) = 0 (.a.)

F(.ab) = 0 (.ab)

Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.

В D хотелось отсечь, но джава, а повышение n может МЛить не аккуратные решения за O(n * 26) памяти. По Е отсекали куб памяти, да и ТЛ 4 секунды намекает.

ou[x][y] the position of the cell (x, y) on the diagonal.

in[x][y] the number and position of the diagonal of the coordinate cell.

hi if you see this comments please do tell me to if you found the ans

if you read the output section carefully you will notice that the problem say " If there are multiple such values, print the minimum of them."

so in your case you can choose any number because all numbers there probability is zero but the minimum one is "1".

How do you use DSU on trees in this problem?

both lead to the same probability of winning. if n=5 and m=3 if we choose a=2, andrew will win for c=1 and c=2 if we choose a=4, andrew will win for c=4 and c=5

Both have same probability and since m-1<m+1, we use m-1. The problem statement states that "If there are multiple such values, print the minimum of them."