You can build $$$n + 1$$$ segment trees where you fix $$$l$$$ for each segment tree. Each segment tree has size $$$O(n)$$$ so you have overall $$$O(n^2)$$$ memory in Segment trees.

Yes, you can encode any rooted tree in $$$O(n log n)$$$ implementing AHU algorithm carefully. You can read more about it here. Then, using the code for a rooted tree is easy to generalize it for an unrooted one because each tree has at most two centroids. So you can call the algorithm for each centroid and merge both vector/strings.

It's also possible to have an $$$O(n)$$$ algorithm if we use radix sort in AHU algorithm. Though I have never implemented it with radix sort but I read about it in this comment. But if I wanted a linear algorithm, I would prefer hashing to receive a simple integer to encode the tree. It's somehow similar to hashing a string and I learned it from this wonderful blog and this paper.

However, I've seen your code for problem G and it seems that you are already familiar with a naive AHU algorithm. So to give you a complete answer I will try to explain how you can go from $$$O(n log^2 n)$$$ to $$$O(n log n)$$$.

If I'm not wrong, what you are doing to encode a rooted tree is the following algorithm:

The size of the code is $$$O(n)$$$ but the algorithm is $$$O(n^2 log n)$$$ because for each node you are sorting a vector of size $$$O(n)$$$. However, for an unrooted tree, as you use the centroid, then each level of the tree will have complexity $$$O(n log n)$$$ and there are $$$O(log n)$$$ levels so the overall complexity is $$$O(n log^2 n)$$$.

Let's optimize it to $$$O(n log n)$$$ for a rooted tree. The problem is that you are storing the complete code for all the subtrees. Instead of that, we can compute something like a "partial code" based only on the children of the node and not on the whole subtree. However, in this new algorithm, we will return a list of integers instead of a string and we're going to process level by level, starting from the deepest level.

The code has size $$$2n - 1$$$ because each node will append 0 (so we have $$$n$$$ zeroes) and each node will have its label appended by its parent, except from the root that has no parent (so $$$n - 1$$$ more integers). And the overall complexity is $$$O(n log n)$$$ because the sum of sizes of all the vectors that we sort is $$$O(n)$$$ instead of $$$O(n^2)$$$ in the naive algorithm.

Here is my implementation to encode a rooted tree (for unrooted tree just encode for each centroid). I hope it helps.

Great tutorial!

I'd like to add some information on something that you mentioned at the end of your blog.

I'm not aware of how to deal with negative cost cycles, and I haven't yet seen it appear in a problem. If you're knowledgeable about negative cycles in MCMF, I'd love to hear about it in the comments.

One possible way to deal with negative cycles is using the cycle cancelling algorithm which is based on, first finding any maximum flow, and then finding negative cost cycle in the residual graph and pushing flow through them. However, its complexity is something like $$$O(nm \times totalCost)$$$, where $$$totalCost = \sum_{e \in E}{cap(e) |cost(e)|}$$$, which is also bounded by $$$mUC$$$, where $$$U$$$ is the maximum capacity and $$$C$$$ the maximum cost in absolute value. This algorithm is also explained in the Lecture notes that you put in the references.

Relevant discussion about MCMF with negative cycles, as well as faster algorithms, can be found in this blog.

One comment of that blog also mentioned a problem where you can test this algorithm (the problem is in Chinese, but it is simply asking for the MCMF with negative cycles). Although the constraints seem too high for the cycle cancelling algorithm, I was able to get AC with it (I used Dinic's algorithm to find the initial flow).

If anyone is interested, I will put a proof here. But it's not a short proof, so I might have overcomplicated it. If anyone has a simpler proof, feel free to share it. Maybe there is some obvious observation that I'm not seeing.

First I need to prove the following lemma.

Then the proof of what you asked for:

Thank you for such a valuable resource. I was recently learning Alien's Trick and this blog helped me a lot to generalize the ideas (although it may be hard to understand at first, as you said). I have some observations/questions about some parts of the blog:

Another important observation to make here is that increasing $$$\lambda$$$ would decrease the size of optimal $$$x$$$ for $$$t(\lambda)$$$ and decreasing it will make more elements positive, thus leading to a larger size of $$$x$$$.

I believe there might be a small mistake here. If I've understood correctly, it's actually the other way around as increasing $$$\lambda$$$ will make more elements satisfy $$$a_i - \lambda \leq 0$$$ so there would be more elements picked in $$$x$$$.

Typical example here is Slater's condition, which says that strong duality holds if $$$f(x)$$$ is convex and there exists $$$x$$$ such that $$$g(x) = 0$$$

I might be wrong here as I was not really familiar with Slater's condition, but after reading some resources, I think that Slater's condition implies that $$$g$$$ needs to be affine because is not of the form $$$f_i(x) \leq 0$$$, or am I missing something ?

I couldn't solve these problems during the contest but I found this paper for "The tortoise and the hare" after the contest ended and I was able to get AC implementing this idea.

I really like the problems. The problemset was very diverse and interesting, although I suppose it was harder for beginners than previous editions. I also like the 24-hour format with few problems being released each hour, it's unique.

However, in all the times that I've participated in this competition, I've never found an editorial after the contest ends (if there is a place where ieeextreme editorials are posted, please let me know). If you could provide an editorial for at least some problems, it would be really appreciated.

I suppose there is a mistake in explanation for problem C as $$$9 + 13 = 22$$$

Solution for D div2 (B div1) without segment trees, sparse table:

After building the difference array $$$D$$$, for each $$$r$$$ we will maintain a list of uniques gcds that we can get if we start at position $$$r$$$ going backwards, i.e. all the possible values of $$$gcd_{l \dots r}=gcd(D_l, D_{l+1}, \dots, D_r)$$$ for all $$$1 \leq l \leq r$$$. Also for each value $$$g$$$ of this list we will also keep the maximum $$$length$$$ such that $$$gcd_{r-lenght+1 \dots r}=g$$$ so that we can update the answer for the problem. We can simulate all this process with a map.

Key observation: The size of the list at each iteration (that is, the number of unique gcds) is $$$O(\log MX)$$$, where $$$MX$$$ is the maximum value of $$$D_i$$$. That's because $$$gcd_{i \dots r}$$$ is a divisor of $$$gcd_{i + 1 \dots r}$$$ for each $$$1 \leq i \lt r$$$. So if $$$gcd_{i \dots r}$$$ is different from $$$gcd_{i + 1 \dots r}$$$, then $$$gcd_{i \dots r} \leq gcd_{i + 1 \dots r} / 2$$$.

Based on that, total complexity will be $$$O(n \cdot \log^2 MX)$$$ (the second $$$log$$$ is for the $$$gcd$$$ complexity). But maybe using the analysis of this blog (also cited in the editorial) the complexity can go down to $$$O(n \cdot \log MX + \log^2 MX)$$$ or $$$O(n \cdot \log MX \cdot \log \log MX + \log^2 MX)$$$ if you take into account the map complexity.

Link to my submission

If you had made the queries to be solved online, wouldn't you have blocked the MO's solutions ?

Although my solution was hacked, it wasn't hacked by you. Am I missing something ?

Why are you sorry ?

In line 32 you should use long long instead of int

Thank you very much

I used another approach in div1-C / div2-E. I'm not sure if my idea is correct. Can someone give me a counterexample (or hack my solution) ?

Submission : 58029374

Idea : sort all the nodes with respect to their degree. First let's try to form an independent set. So we iterate through the nodes and if it isn't marked, then we add it to our list and marked all its neighbours. If the list has size >= n , we're done . If size < n , we do almost the same in order to find a matching. In the same order we iterate through the nodes and if it isn't visited we try to find a neighbour that is not visited. If we find such a pair, we add it to our list of matching and we visit both nodes. But I'm not sure if this matching has size >= n in all the cases.

please rated