Here is the solution to G-Bonus (solution using purely generating functions).

if we let $$$T_{n,l}$$$ represent the number of valid permutations on all labelled trees with $$$n$$$ vertices and $$$"l$$$ leaves, and let

then we have the following recurrence relation

where $C \left( n_1, \cdots , n_r \right)$ is the function that counts the number of partitions of $$${ 1,\cdots,n_1+\cdots+n_r+1 }$$$ into sets of sizes $$$1,n_1,n_2,...,n_r$$$ respectively (For example $$$C(2,1) = \frac{4!}{2!1!} = 12$$$ and $$$C(2,2) = \frac{5!}{2!2!2!} = 15$$$). In terms of generating functions, this becomes

Taking partial derivative w.r.t $x$, we get

Integrating w.r.t $$$x$$$, we get

Comparing coefficients of $x^0 y^m$ on both sides for all $$$m \geq 0$$$, we have that $$$c(y) = \frac{y}{1-y}$$$. Thus for $$$n \geq 1$$$, we have that

Expanding this further, we get

We must have $r=n$ and $$$r-m=l$$$ to get the required coefficient. Substituting this we get

Taking $$$k = n-m-l$$$, we can re-write the summation as follows

Now, since the coefficient in $$$t(x,y)$$$ is equal to $$$\frac{T_{n,l}}{(2n)! \ (n)!}$$$, we have that

Now, since the root is fixed, we must divide by $n$ to get only labelled trees having $$$1$$$ as the root.

Thanks!

I am having a hard time trying to prove that the only constraints on the flows at any stage are on the sum of subsets. In particular, why are the only non-redundant constraints on flows in form of constraints on subset-sum? Can there be a non-trivial constraint with non-binary coefficients? Does anyone have some material I can read up?

what does this line mean in editorial of $$$H$$$?

Let b_i be the number of operations that has the element equal to v after block y_i as its center

I couldn't understand the rest of the editorial because of that

I think the problem is solvable in something like $$$n\cdot\log(n)^2$$$, more precisely, it's $$$\sigma(n)\cdot\log(n)\cdot\omega(n)$$$, where $$$\sigma(n)$$$ is the sum of divisors of $$$n$$$ and $$$\omega(n)$$$ is the number of prime factors of $$$n$$$.

First, we come up with a function $$$g(x,d) \ \forall \ d \ |\ n, 0\le x \lt d$$$ (there are $$$\sigma(n)$$$ such values we need to calculate), and we'll calculate these values in decreasing order of the divisors.

We define

Now, notice that if $d = p \cdot q$ for some prime factor $$$p$$$ of $$$d$$$, then

which takes $O(p)$ time to compute for a given $$$y$$$. Since there are $$$q$$$ such values, the total computation time is $$$O(p\cdot q) = O(d)$$$ So, when iterating over the divisors in decreasing order, after we've computed the values of $$$g(x,d)$$$ for all $$$0 \le x \lt d$$$, we'll be doing this computation for all prime factors of $$$d$$$, which makes the overall complexity $$$O(d\cdot \omega(d))$$$. Since we're iterating in descending order of divisors, when we reach a given divisor, we would have already computed its set of values, and we can do the similar thing for all its prime factors.

Total complexity hence turns out to be $$$\sum_{d \ | \ n} O(d \cdot \omega(d)) = \sigma(n) * \omega(n)$$$. I believe the complexity could even be brought further down if we are somehow smarter about which prime factors to consider, as one divisor would have been calculated multiple times in this approach.

https://codeforces.me/contest/1905/submission/237719024 this solution is O(N). I've used hashmap to store the pair of swaps, so that should be O(N) too.

Consider the longest palindromic substring of $$$Str$$$, call it $$$P = \{ p_1, p_2, ..., p_n \}$$$. Then \we must have that $$$p_i = p_{n+1-i} \forall \ 1\leq i\leq n$$$.

Now, remove this substring from $$$Str$$$, and assign the left-half substring to $$$s_1$$$ and reverse of the right-half substring to $$$s_2$$$. So, the the assignment will look like

where $a$ denotes that this position belongs to the left-half substring and $$$b$$$ denotes that it belongs to the right half sub-string. Now, we're going to construct the string $$$T$$$ as follows

Notice that for this sub-string,

and

I will provide a construction as well as a proof of optimality. First, let's start with a proof of optimality. notice that $$$LCS(Str, reverse(T)) = LCS(reverse(Str), T)$$$. Now, let's say $$$s_1 = LCS(Str, T)$$$ and $$$s_2 = LCS(reverse(Str), T)$$$. Then, we must have that

As $$$T$$$ must be an intertwining of the sub-sequences $$$s_1$$$ and $$$s_2$$$ with some positions that are common to both of them, and some positions that belong to neither of them. Here $$$s_1 \cap s_2$$$ denotes the positions in $$$T$$$ that are common to both $$$s_1$$$ and $$$s_2$$$. Now, notice that $$$s_1 \cap s_2 \leq |LCS(s_1, s_2)|$$$. Therefore, we must have that

But $s_1$ is a sub-sequence of $$$Str$$$, and $$$s_2$$$ is a sub-sequence of $$$reverse(Str)$$$. Therefore,

which is the length of longest palindromic substring. Hence,

Which implies that

I will provide the construction in another comment.

I think the answer is $$$\lfloor\frac{n + |P|}{2}\rfloor$$$, where $$$|P|$$$ is the maximum palindrome size.

Sorry, let me try to explain what I really meant.

Consider any node for which we're trying to find the answer right now. If it has a child with size greater than $$$(size\text{_} of\text{_} subtree)/2$$$, then we don't need to perform this computation for that node (the best partition is to put the heaviest node on one side and the rest on the other), and we can directly move to this heaviest node and perform this same computation there. Otherwise, we will need to perform this computation (taking $$$sz \log^2(sz)$$$ computation).

Then all children of this node have subtree size less than or equal to $$$sz/2$$$, and we'll be performing the same computation for each of them. However, notice that whenever we perform a computation, the maximum size of any sub-tree we would be dealing with would not exceed half of $$$sz$$$.

Thus, we can think of it as performing computations at different levels. At the first level, the size of each node is less than or equal to $$$sz$$$, then at the second level, the size is less than or equal to $$$sz/2$$$, at the third one, it's less than $$$sz/4$$$ and so on, thus there can be at most $$$\log(sz)$$$ levels, and the computation at each level, when summed over all the nodes at that level, would require at most $$$sz \log^2(sz)$$$ computations, giving $$$sz \log^3 (sz)$$$ overall.

E can be solved in $$$n \log^3(n)$$$ using FFT.

Consider the sizes of children of each node — say for a node $$$u$$$, the sizes of child node sub-trees are $$$s_1, s_2, ... , s_c$$$. Then, consider the polynomial $$$(1 + x^{s_1})(1 + x^{s_2})\cdots...(1 + x^{s_c})$$$. The coefficients of this polynomial can be computed in $$$n \log(c) \log(n)$$$. Once we have these coefficients, we will find the closest number to $$$n/2$$$ having non-zero coefficient in the final polynomial. We'll only do this when each child node has size smaller than $$$n/2$$$. Thus, we'll need to do this polynomial computation at most $$$\log(n)$$$ times.

this gives overall time complexity of $$$n \log^2(n) * \log(n)$$$

The solution for G is a bit strange.

If there exist two segments (l1,r1),(l2,r2) such that l1≤l2≤r2≤r1 and we choose (l1,r1), number of >ways of choosing (l2,r2) at the same time will be equal to that of not choosing. Hence if we >choose (l1,r1), the signed number of ways will be 0. So we can delete (l1,r1).

This is not true. For eg. if the segments are $$$[1,3],[4,6],[2,5],[3,4]$$$ and $$$[l,r]$$$ is $$$[1,6]$$$, then the answer is equal to $$$1$$$ (not zero) and also $$$[2,5]$$$ contains the segment $$$[3,4]$$$.

Thanks. Didn't read the question properly

For C, the alternate solution in the editorial doesn't seem right. An counter-example is $$$ababa$$$. The answer for this is $$$ba$$$ which is not a generator of the input string.

What is the solution for F Bonus?

I am able to prove a linear bound for it, but not able to prove the exact bound you mention.

Here is a brief sketch of the proof. Consider the important segments at a given level, say $$$lvl$$$. By important segments at a level $$$lvl$$$, I mean all the important segments for which the answer is equal to $$$lvl$$$. So for $$$level=0, [0,n-1]$$$ is the only important segment, and so on.

Now, a small detour — instead of looking at segments like $$$[l,l+1,...r]$$$ look at them as $$$[l,l+1],\cdots,[r-1,r]$$$. So, when I say the endpoints of a segment, I mean $$$[l,l+1]$$$ and $$$[r-1,r]$$$. If the segment has just two points, then it has only one unique endpoint. Now, consider that we're at level $$$lvl+1$$$, and we want to find all the important segments at this level. Then consider the end-points of all the important segments at all the previous levels (endpoint defined as above). My claim is that

• There can't be any important segment at $$$lvl+1$$$ that strictly contains any of these end-points. So, for any end-point, either it's outside of a segment at this level, or, it's the end-point for that segment, but it can't be strictly inside.

• Segments at the same level can only share up to an end-point. i.e. they can either be disjoint, or touch each other at a point, or have a common end-point (have two points in common)

The proof of this claim is using induction. For the first part of the claim, say there was an important segment $$$[l',r']$$$ at this level strictly containing a previously occurred endpoint $$$[i,i+1]$$$. Then since this end-point must have been the end-point of some imp. segment previously, WLOG $$$[i, j]$$$ was the imp. segment at previous level. then, $$$f([i, j])$$$ must be either equal to the entire array, or it must contain some imp. segment $$$[a,b]$$$ at a previous level. Now, if its image contains some segment at a previous level, then notice that $$$f([i+1,j-1])$$$ must be strictly inside such a segment (not even touching the ends), more precisely, $$$f([i+1,j-1])\subseteq [a+1,b-1]$$$. If not, then there could have been a smaller segment containing this segment, which is a contradiction. Similar argument can be applied for when the image is equal to the entire array, as if $$$f([i+1,j-1])$$$ was touching any of the ends of the array, we would have had a smaller segment and the segment wouldn't be important.

Now, $$$r \lt j$$$ (as the contrary would imply $$$[l,r]$$$ contains $$$[i,j]$$$), so $$$r \in [i+1,j-1]$$$ and hence $$$f([r])$$$ falls strictly inside the segment $$$[a,b]$$$. Also, for $$$[l,r]$$$ to be an important segment at $$$lvl+1$$$, there must be a segment at previous level that is inside $$$f([l,r])$$$. But notice that by our induction hypothesis, any such segment must either be disjoint with $$$[a,b]$$$, or inside it completely, or outside it but touching $$$[a,b]$$$ at one end, or inside/outside it but intersecting with $$$[a,b]$$$ at exactly one endpoint. One can show that for all possible scenarios, either $$$f([l,i+1])$$$ contains this segment, or $$$f([i,r])$$$ contains it, and our induction hypothesis is true. Similar arguments can be applied to prove the second part of the claim.

Using this observation, we can deduce that each end-point, when introduced at any level, can be part of two segments (one to the left and one to the right). and finally, all end-points themselves can be imp. segments, giving an upper bound of roughly $$$3n-6$$$.

Can you please explain this approach in more detail? How will passing the card in the j-th permutation ensure that they all will be eventually sorted?

Consider the frequencies of all elements in the array in sorted order — say $$$f_1 \le f_2 \le \cdots \le f_n$$$. Now, when you pair two unequal elements and remove them from this array, two distinct $$$f_i$$$s decrease by exactly one. Now think when would it not be possible to pair unequal elements any further in this array? When either the array is empty or there is only one unique element remaining in this array, i.e. $$$f_i \gt 0$$$ for only one element and $$$f_j = 0$$$ for all other elements. Thus, we want to avoid the latter situation, so we try to always pair maximum frequency elements.

Another way to visualize this is we're trying to sweep a skyline of towers, two floors at a time from different buildings. The structure $$$f_1 \le f_2 \le \cdots \le f_n$$$ is analogous to a skyline structure and we're removing floors from the towers of this structure. The best way to ensure we remove as many floors as possible, given that we can remove only two floors at a time from different buildings, is that we remove them from the towers with the maximum height, so that in the end we reach a point where all towers have height at most one.

Problem E1/E2 also has a O( L ) solution, but it is an implementation nightmare, and the constant overhead possibly makes it worse than the O( L*Log L ) solution. The idea is to consider the cases when deletions are from both the strings, and the first string deletion is to the left of second string deletion, when it is to the right of it, and finally when deletion happens in only either the first string or the second string — https://codeforces.me/contest/1393/submission/89457260

Someone posted that problem F is actually same as this https://codeforces.me/gym/101438 problem, and the editorial of that contest provides a much better explanation in terms of LCS, which is not NP-Hard.

The reason I'm doubting the solution is that the following version of the problem: where instead of right rotations, we swap the elements, is NP-hard. See this : https://stackoverflow.com/questions/18292202/finding-the-minimum-number-of-swaps-to-convert-one-string-to-another-where-the

Can anyone give a rigourous proof for the dp solution for f. What does the dp state define?

I figured out a solution that uses no matching at all, just some Modular Arithmetic and a manageable case-by-case breakdown. Here is a link to the explanation of the solution and working code ($$$O(n^2)$$$ algorithm).

Link : https://drive.google.com/open?id=1FUW3SovjVZMNHbo_I-zA0RZtcirwyA2d

Can anyone explain Div1D. I have no idea what the editorial is saying.

Do you have a solid proof for why just comparing parities of zero positions works?

The language of the question is a bit confusing. Does this line — "It is also known that if all spells are used, each child will receive at most $$$k$$$ candies." mean that the intervals that are supplied already satisfy this criteria or does it mean that our selection of intervals should be such that this criteria is satisfied (i.e. at most $$$k$$$ intervals pass through one point)? because I think only in the latter case this algorithm would work.

Can anyone explain D. What do those bits represent. For ex. what would the state <i = 2, mask = 0 0 1 0 1 0 0 0> represent, and what does dp calculate (I guess it gives the maximum score for that particular state but I am not sure). I am not getting any ideas. Also, I am not completely convinced <i-1, all masks> -> <i, all masks> because for the case when k = 1, this won't work.

Got it, thanks. Also how does someone come up with such ideas. Seems quite out of the blue.

I don't understand how complexity of F is $$$n*log(n)$$$. The number of non-overlapping rest stops for a given node can be very large, and I have a concrete counter-example for $$$O(n^2)$$$, if I understand the editorial correctly. Can anyone please explain proof of complexity.