A. Meaning Mean
Author: athin
Developer: ArvinCiu
Editorial: Kinon
Tutorial
B. Maximize Mex
Author: joelgun14
Developer: joelgun14, CyberSleeper
Editorial: Pyqe
Tutorial
C. Adjust The Presentation
Author: ArvinCiu
Developer: icebear30, gansixeneh
Editorial: ArvinCiu, gansixeneh
Tutorial
D. Boss, Thirsty
Author: ArvinCiu
Developer: CyberSleeper
Editorial: Pyqe
Tutorial
E. Digital Village
Author: CyberSleeper
Developer: ArvinCiu
Tutorial
Brute force in $$$\mathcal{O}(nm^2)$$$ can pass problem D.
Submission
Hacked :)
Segment tree for C2 seems like a bit of overkill. You can keep vector of sets of indices in b for each element of a. (including m+i, or just any large const, if you allow non-strict increasing arrays instead). Then, for each update you just need to check whether the increase condition still holds for the adjacent pairs and update the counter. If the counter is full, yield YA.
FINALLY.
Ha-ha, not for E yet:)
My solution to E3:
Call a node "special" if it is one of the $$$p$$$ given nodes. Call a node "chosen" if it is one of the $$$k$$$ nodes in the chosen subset.
Build the Kruskal Reconstruction Tree (KRT) of the graph, with $$$2n - 1$$$ nodes. All nodes in the original graph are given the same label in the KRT.
For some special node $$$x$$$, let $$$y$$$ be the lowest ancestor of $$$x$$$ in the KRT with at least one chosen node in the subtree of $$$y$$$. The maximum edge weight needed to get to a chosen node from special node $$$x$$$ in the original graph, is the weight of the edge that corresponds to $$$y$$$ in the KRT.
I then transformed this problem a bit. Let $$$f(i)$$$ be the edge weight that corresponds to node $$$i$$$ in the KRT (if $$$i \leq n$$$, then $$$f(i) = 0$$$). Let $$$g(i)$$$ be the number of special leaves in the subtree of $$$i$$$ in the KRT. Let the the value of a node $$$i$$$ be $$$g(i) * (f(i) - f(par[i]))$$$. Choose $$$k$$$ leaves in the KRT, to minimize the sum of values of nodes which have at least one chosen leaf in its subtree.
This works, because the contribution of some special node $$$x$$$ will be $$$(f(y) - f(par[y])) + (f(par[y]) - f(par[par[y]])) + \dots = f(y)$$$, where $$$y$$$ is the lowest ancestor of $$$x$$$ with a special node in its subtree.
Construct the subset of leaves one by one. Keep choosing the leaf which will have the least contribution.
To simulate this quickly, let $$$h(i)$$$ be the highest ancestor of leaf $$$i$$$, such that leaf $$$i$$$ is the leaf that minimizes the sum of values on the path from $$$i$$$ to $$$h(i)$$$. Initially, you must take the leaf $$$i$$$ which has $$$h(i)$$$ = the root of the tree. Sort the rest of the leaves in increasing order of the sum of values on the path from $$$i$$$ to $$$h(i)$$$, and add them to the subset in that order.
Let $$$dp[i][j]$$$ be the minimum sum of values of nodes when choosing $$$j$$$ leaves in the subtree of $$$i$$$.
If $$$j = 0$$$, then $$$dp[i][j] = 0$$$. Otherwise, $$$dp[i][j] = val[i] + min(dp[left][x] + dp[right][j - x])$$$, where $$$0 \leq x \leq j$$$, and $$$left$$$ and $$$right$$$ are the children of $$$i$$$ in the KRT. To optimize this DP for E3, notice that the values of $$$dp[i]$$$ are convex. $$$dp[i][j] - dp[i][j - 1] \leq dp[i][j + 1] - dp[i][j]$$$ holds.
Doing the transformation $$$c[j] = min(a[x] + b[j - x])$$$ when arrays $$$a$$$ and $$$b$$$ are convex, can be done by merging the slopes of arrays $$$a$$$ and $$$b$$$. (See this errorgorn blog).
You can maintain the slopes of the dp in a sorted multiset, and merge the multisets of the left and right children into $$$dp[node]$$$, and then insert $$$val[node]$$$ into $$$dp[node]$$$.
After this round my rating increased to 1399, and i am very grateful to the rating system.