Weekly training farm 23 editorial (drazil part)

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Sorry for the delay but here is the (partial) editorial of 23rd weekly training farm. I set up 3 problems (B, C, F) in this contest. Here is the link to the contest: http://codeforces.me/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 $\text{[math]}$ 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 $\text{[math]}$ 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 $\text{[math]}$ , 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 the decending order, we have $\text{[math]}$ 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!

C. tree split

This problem is equivelent to: Is there a way to remove some edges in a tree so that the remaing 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₁ and N₂. The key observation is that if both N₁ and N₂ is a multiple of 3 for an edge, then this edge needs to be removed. Moreover, if N₁ is a multiple of 3 then N₂ 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 inderect comparison, direct comparison 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²) time. The size of such set would be the answer since any permutation of this set of characters would work.