Задача A.
$$$a_2 - a_1 + a_3 - a_2 + \ldots + a_n - a_{n - 1} = a_n - a_1$$$. А значит нам нужно просто максимизировать это значение, а значит ответ максимальное число в массиве минус минимальное.
Задача B.
Давайте заметим, что каждая клетка задевает не более двух диагоналей, поэтому ответ на задачу хотя бы $$$\frac{k + 1}{2}$$$.
Утверждение: посмотрим на конструкцию, где мы в первой строке красим все клетки. А в последней все, кроме двух боковых. Тогда каждая такая клетка соответствует ровно двум диагоналям. И если $$$k \leq (2n - 2) * 2$$$, то ответ ровно $$$\frac{k + 1}{2}$$$.
Теперь заметим, что если у нас закрашены $$$2n - 1$$$ или же $$$2n$$$ клеток, то одна или две клетки соответсвенно будут соответствовать ровно одной диагонале, потому что в этом случае мы обязаны закрасить боковые клетки, ибо это единственные диагонали, которые мы не задели, а они уже покрываются другой диагональю, которой соответствует другая угловая клетка.
А значит ответ в случае $$$4n - 3$$$ такой же ввиду четности, а для $$$4n - 2$$$ это $$$\frac{k}{2} + 1$$$.
Задача C.
Давайте заметим, что условие, что мы можем получить сколь угодно большое значение означает, что нам необходимо получить гарантированно хотя бы $$$+1$$$ к нашим монетам. При первой же победе. В этом случае мы можем повторять данную стратегию бесконечно много раз.
Также заметим, что если мы до этого проиграли суммарно $$$z$$$, то в следующий раунд нам необходимо поставить $$$y$$$ такое, чтобы $$$y \cdot (k - 1) > z$$$, так как иначе казино может отдать нам победу. В этом случае условие на проигрыш не более $$$x$$$ раз подряд пропадет, а мы ушли в минус. А следовательно тактика является не оптимальной.
А значит решение — мы ставим сначала $$$1$$$, затем мы ставим минимальное число, чтобы победа перекрыла наш проигрыш. И если нам хватит на $$$x + 1$$$ то такую ставку, то казино обязано уйти в минус, иначе же мы не сможем победить.
И получается решение за $$$O(x)$$$, где мы просто циклом считаем эти значения.
Задача D.
Пусть $$$dp_v$$$ — это количество непустых множеств вершин в поддереве $$$v$$$ таких что, нет ни одной пары вершин в множестве, где одна вершина является предком другой.
Тогда $$$dp_v = (dp_{u_1} + 1) \cdot (dp_{u_2} + 1) \cdot \ldots \cdot (dp_{u_k} + 1)$$$, где $$$u_1, \ldots, u_k$$$ — это дети вершины $$$v$$$. Так как из каждого поддерева можно выбрать либо любое непустое множество, а также пустое. А выбор из каждого поддерева пустого множества означает, что выбрали единственную вершину $$$v$$$. (так как в нашей динамике не может быть пустого множества).
Теперь утверждение: ответ на задачу это $$$dp_1 + dp_2 + \ldots + dp_n + 1$$$. Так как если мы говорим, что пусть у нас есть пара вершин, где вершина $$$v$$$ является предком другой. Тогда ответ в этом случае это $$$dp_{u_1} + \ldots + dp_{u_k}$$$, так как мы можем выбрать ровно из одного поддерева такое множество вершин из динамики. (И как раз здесь мы используем непустые множества в состоянии динамики, ибо иначе учитывался вариант, где одна нет вершин, где одна предок другой). А $$$dp_1 + 1$$$ (где $$$1$$$ — это корень дерева) отвечает за варианты, где нет вершины, где одна вершина является предком другой.
Задача E.
Давайте для каждого ребра $$$i$$$ отметим множество пар $$$S_i$$$, которое оно перекрывает. Тогда утверждение: У нас различных множеств $$$O(k)$$$. Так как нас интересуют только ребра, которые находятся в сжатом дереве на этих $$$k$$$ пар вершин. А как известно, ребер в сжатом дереве $$$O(k)$$$.
Тогда нам нужно среди этих множеств выбрать минимальное количество такое, что каждая пара находится хотя бы в одном из них. А это делается динамикой по множествам следующим образом:
Пусть $$$dp[mask]$$$ — это минимальное количество ребер, которые нужно удалить, чтобы были в парах соответсвующим единичным битам из $$$mask$$$ было вычеркнуто хотя бы одно ребро.
Тогда пересчет следующий $$$dp[mask | S_i] = min(dp[mask | S_i], dp[mask] + 1)$$$ по всем различным множествам $$$S$$$, где $$$S_i$$$ это маска соответсвующая парам, которые проходят через ребро. А пересчет такой, так как мы к этой маске добавляем еще одно ребро.
В итоге получаем решение за $$$O(nk + 2^k k)$$$, где за $$$O(nk)$$$ мы для каждого ребра предпосчитываем множество пар, которое оно вычеркивает, а $$$O(2^k k)$$$ это пересчет динамики.
Задача F.
Давайте выпишем номера вершин в порядке их значений. Пусть это $$$v_1, \ldots, v_n$$$. Тогда должно выполняться $$$value_{v_i} \leq value_{v_{i + 1}}$$$.
Тогда у нас есть некоторые отрезки в этом порядке, для которых нам значения не известны. Тогда нам для каждого отрезка известно максимальное и минимальное значение, которое могут принимать значения на этом отрезке, пусть это $$$L$$$ и $$$R$$$. Тогда нам нужно для каждого числа на этом отрезке выбрать значение из отрезка $$$(L, R)$$$, чтобы сохранялся относительный порядок. А это известная задача и таких вариантов $$$\binom{R - L + len}{len}$$$, где $$$len$$$ это размер отрезка. А затем нужно перемножить все эти биноминальные коеффициенты.
Теперь заметим, что у нас $$$R - L + len$$$ большое, поэтому для подсчета можно просто воспользоваться формулой $$$\binom{n}{k} = \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1)}{k!}$$$, так как сумма $$$len$$$ не превосходит $$$n$$$.
