Sorry for the delay but here is the (partial) editorial of 23rd weekly training farm.↵
↵
I set up $3$ problems (B,CE, F) in this contest.↵
↵
Here is the link to the contest: http://codeforces.net/group/gRkn7bDfsN/contest/211543↵
↵
===================================================================================================↵
↵
B. cut down↵
↵
The idea of the problem is from this deep learning paper: Martins, André FT, and Ramón Fernandez Astudillo. "From softmax to sparsemax: A sparse model of attention and multi-label classification." CoRR, abs/1602.02068 (2016). You can read the paper here: https://arxiv.org/abs/1602.02068↵
↵
You can use binary search to find the answer in $O(N\log{N})$ time. But what if I ask you to output the exact answer (in the form of division of two integers $p/q$) instead of a floating point number? That problem can be solved in $O(N\log{N})$ time, too! Actually, if the input is sorted, $O(N)$ time is sufficient for the problem!↵
↵
Let's consider a simplified problem first, can you check if there is a valid $T$ satisfying $T < A_i$ for all $i$? The solution is to assume that such $T$ exists which implies $T = [(\sum\limits_{i=1}^{N} A_i) - X] / N$, then verify if $T$ is less than the smallest $A_i$.↵
↵
To solve the original problem, we need one more observation: After sorting $A$ in descending order, we have $T = [(\sum\limits_{i=1}^{k} A_i) - X] / k$ where $k$ is the largest number that the above simplified problem is true. So we can maintain a partial sum to find the value of $k$ and the answer in $O(N)$ time after sorting.↵
↵
Furthermore, the original problem can be solved in $O(N)$ time overall (even with unsorted input) using linear selection algorithm!↵
↵
CE. tree split↵
↵
This problem is equivalent to: Is there a way to remove some edges in a tree so that the remaining forest is consists of $3$ vertices trees?↵
↵
Removing an edge in the given tree splits all vertices into two trees. Let's denote the number of the vertices in the two resulting trees as $N_1$ and $N_2$. The key observation is that if both $N_1$ and $N_2$ is a multiple of $3$ for an edge, then this edge needs to be removed. Moreover, if $N_1$ is a multiple of $3$ then $N_2$ must be a multiple of $3$! So a dfs on the vertices maintaining the number of visited vertices can count the number of edges to remove in $O(N)$ time.↵
↵
Finally, we just need to check if removing those edges will result in a forest of exactly $N$ trees. This can be assured if the number of edges removed is equal to $N-1$.↵
↵
F. Strings↵
↵
The key observation is that although we allow indirect comparison, direct comparisons is still required for every pair of vocabularies to ensure a unique order. In addition, to compare two strings we just need to define the order of the first different character of the two strings. So we can brute force every pair of vocabularies and find out the set of the characters need to be defined in $O(N^2)$ time. The size of such set would be the answer since any permutation of this set of characters would work.
↵
I set up $3$ problems (B,
↵
Here is the link to the contest: http://codeforces.net/group/gRkn7bDfsN/contest/211543↵
↵
===================================================================================================↵
↵
B. cut down↵
↵
The idea of the problem is from this deep learning paper: Martins, André FT, and Ramón Fernandez Astudillo. "From softmax to sparsemax: A sparse model of attention and multi-label classification." CoRR, abs/1602.02068 (2016). You can read the paper here: https://arxiv.org/abs/1602.02068↵
↵
You can use binary search to find the answer in $O(N\log{N})$ time. But what if I ask you to output the exact answer (in the form of division of two integers $p/q$) instead of a floating point number? That problem can be solved in $O(N\log{N})$ time, too! Actually, if the input is sorted, $O(N)$ time is sufficient for the problem!↵
↵
Let's consider a simplified problem first, can you check if there is a valid $T$ satisfying $T < A_i$ for all $i$? The solution is to assume that such $T$ exists which implies $T = [(\sum\limits_{i=1}^{N} A_i) - X] / N$, then verify if $T$ is less than the smallest $A_i$.↵
↵
To solve the original problem, we need one more observation: After sorting $A$ in descending order, we have $T = [(\sum\limits_{i=1}^{k} A_i) - X] / k$ where $k$ is the largest number that the above simplified problem is true. So we can maintain a partial sum to find the value of $k$ and the answer in $O(N)$ time after sorting.↵
↵
Furthermore, the original problem can be solved in $O(N)$ time overall (even with unsorted input) using linear selection algorithm!↵
↵
↵
This problem is equivalent to: Is there a way to remove some edges in a tree so that the remaining forest is consists of $3$ vertices trees?↵
↵
Removing an edge in the given tree splits all vertices into two trees. Let's denote the number of the vertices in the two resulting trees as $N_1$ and $N_2$. The key observation is that if both $N_1$ and $N_2$ is a multiple of $3$ for an edge, then this edge needs to be removed. Moreover, if $N_1$ is a multiple of $3$ then $N_2$ must be a multiple of $3$! So a dfs on the vertices maintaining the number of visited vertices can count the number of edges to remove in $O(N)$ time.↵
↵
Finally, we just need to check if removing those edges will result in a forest of exactly $N$ trees. This can be assured if the number of edges removed is equal to $N-1$.↵
↵
F. Strings↵
↵
The key observation is that although we allow indirect comparison, direct comparisons is still required for every pair of vocabularies to ensure a unique order. In addition, to compare two strings we just need to define the order of the first different character of the two strings. So we can brute force every pair of vocabularies and find out the set of the characters need to be defined in $O(N^2)$ time. The size of such set would be the answer since any permutation of this set of characters would work.
