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, (max, +) convolution part).
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]$$$.
The moment I read the problem I instantly saw that it would be DP or greedy on KRT lol
Is KRT such a known topic? Honestly, I've never heard of it before reading this explanation. From what I've read it's used to compute the biggest edge on a path between two nodes of a tree in O(1), which is super cool but until now I've never had to do it
I learned it when I was training for Balkan OI, I don't think its such a known topic but its very cool
Alternate much simpler solutio : split over largest edge and solve the 2 subproblems and then merge
This is O(n^2) dp [each pair of nodes contributes exactly once]
To optimize, do same as the dp solution, convex => store slopes in multiset and small to large
Isn't this the same as my solution? I just preprocess the part of splitting over largest edge
well you dont need any KRT. also do you have a proof for your greedy solution? WHy is the optimal subset for i + 1 necessarily a superset of subset for i
The last paragraph is quite unclear to me, maybe because I am quite unfamiliar with it(convex,slopes in this problem's context), but how does it work here exactly.
the comment i replied to had already linked errorgorns blog about it.
Nevertheless, suppose you want to compute array c where c[k] = min(a[i] + b[j]) such that i + j = k, and you know both a and b are convex, then you can prove that if you consider the adjacent differences of a, and the adjacent differences of b, and merge them together, you get the necessary adjacent differences of c.
from here, you can store the dp states as multisets of adjacent differences, and then merge the multisets using small to large to maintain nlog^2 complexity. the largest element needs to be kept track of separately fyi. https://mirror.codeforces.com/contest/2021/submission/284859127
wish to reach this level someday
Bro can you please tell what approach did you use in E2 or what that technique is called?
During the contest I can only come up with O(n^2) DP. Seems I didn't realize KRT is a binary tree and didn't come up with slope storing. BTW, the Greedy is such a wonderful solution! This indicates that we can also consider every node's contribution instead of pair of leaves. It gives me a huge inspiration.
After this round my rating increased to 1399, and i am very grateful to the rating system.
You will probably get +1 on the next rating rollback
E is very nice. Learn a new trick about how to use minimum spanning tree in this.
Btw, editorial E only E3 ?!
For E1 you can easily do floyd-warshall to compute all the distances in O(N^3). Then you can find the solution for all Ks choosing where it's most optimal to place the next server, knowing that the K-1 servers chosen before stay the same.
For E2 you can do a DP, merging solutions for subgraphs (connected components) by using a DSU and processing each edge in order of weight. Merging two subgraphs A and B, it's optimal for the houses that need wifi to stay connected to the servers in their own component, so you simply sum the total latencies of both subgraphs. If one of the subgraphs has no servers (A) and do other does (B) then all the houses in A that need wifi need to reach the servers in B, passing through the edge currently being processed, which is the heaviest, so you sum the total latency of B with the weight of the current edge multiplied by the number of houses in A that need wifi.
Here are my solutions: E1 : https://mirror.codeforces.com/contest/2021/submission/284593507 E2 : https://mirror.codeforces.com/contest/2021/submission/284974748 (I learned from tourist's submission and added some comments)
How do you prove that K-1 servers stay the same? I mean, you don't need to prove it to submit and get AC, but you need to convince yourself that it worth putting in the effort.
How do you prove the conclusion of E1 by theory but not your submission？This conclusion is important.
I was gonna say D is chaotic until I saw this implementation (ecnerwala's). Insane
athin Kinon "It turns out that the strategy above is also the optimal strategy for the original version of the problem. So we can simulate that process to get the answer" proof please?
Explain to me, plz, algorithm for E1. Most of the solutions use Floyd-Warshall algorithm to calculate distances between vertices. Then for each k they greedily find next vertex to install server, and this vertex should reduce current latency the most. So if we have set of vertices-servers on the step k, then solution for k+1 contains all these vertices plus another one that have met the criteria I've described above. While it's clear for me that we should install servers in vertices where we need servers (and do not consider other vertices as candidates), it's more complicated to prove optimality of greediness on each step for k. Can you explain me, why greedy solution would be globally optimal?
For example, for k=1 I have to put server in vertex, say, 3. Why it's not possible for k=2 to have set of vertices (1, 2) as optimal solution so that latency of (1, 2) solution is less than (3, 1) or (3, 2) or any other (3, *) solutions?
It felt intuitive for me but only after implementing it. As you said "this vertex should reduce current latency the most". The target of what we are greedily minimizing is the sum of minimum current latencies considering servers chosen so far. So let's try the following:
For 1 server, to find minimum total latency, we can choose greedily the house where the sum of latencies after choosing that house is the minimum. Seems obviously true.
Assume for some k servers placed, we have chosen k servers that reduce total latency (sum of current latencies for each internet house) the most and this is optimal. Then for k+1 servers, lets choose from the remaining houses the house that reduces the total latency the most. Had we picked some other house, then the total latency would have been greater or equal.
So it should be true for all k by induction. Feel free to correct if this is wrong.
The first thing to do when proving a greedy algorithm is to make sure that the decision made on the first step doesn't block the path to the optimal solution.
In your reasoning you don't check this condition. And the example, that I gave in the previous comment, shows that. You greedily install server in vertex 3 because it reduces the current latency the most. But it's not clear why this step doesn't block the way to the solution on step k=2 where set of vertices (1, 2) could be better and have less latency than any other (3, *).
To finally clarify what I mean, let's consider a greedy approach to the knapsack problem. You have knapsack with capacity 6, indivisible (so you can't divide object into parts) items with weights 2, 2, 2, 5 and their costs 4, 4, 4, 5 accordingly. Greedy algorithm would take item with weight 5 because it has the highest cost and give us non-optimal solution with the cost of 5 while dp would find optimal solution putting first three items in knapsack and making a cost equal 12. Let's look at what we'd get if we try to prove that our greediness gives us optimal solution using induction. Target is clear: we should maximize the total cost of the items in the knapsack. First, we choose the item with the highest cost (similar to how you choose where to install first server) because it increases cost the most (you see, exactly like you did in your proof). We put him in the bag, and it turns out that we would never get the correct answer because none of the left items fit in our knapsack anymore. That's because our first step blocks optimal solution, and we should check this before continuing the proof by induction.
I hope I was clear. Also, if you see any mistake, be sure to let me know. And thanks for your answer.
I think the difference is we don't have any cost constraint on what to choose, unlike in the knapsack case. So we can keep choosing. Another way of thinking is instead of blocking the path to the optimal solution, what if we show what we found is already optimal. That's what I went with. Also, we can definitely have different vertices being optimal, but only with equality, never with strict inequality.
Please make Editorial for each part of the problem E.Both solutions for C2 had a level of math observation way beyond me, I solved C1 almost exactly mentioned in the editorial yet failed to even come close to the required idea for C2. Anyway segtree seemed the more approachable of the two so here's a segtree submission which is relatively clean for reference: https://mirror.codeforces.com/contest/2021/submission/285002624
Super slow editorial :(
I waited for days to see the official editorial for E3 and what I see now is
coming soon. The time is enough to see the accepted code by myself and understand the idea of KRT.Editorial for E1&E2:
Firstly, it is not hard to find out that the graph can be reduced to its minimum spanning tree since only the max value on the path is concerned.
Now, suppose the tree $$$T$$$ is in the form of $$$A-e-B$$$, where A and B are two subtrees and $$$e$$$ is the edge of the large value in the graph. Define $$$DP_A[i]$$$ where $$$(1\le i \le n))$$$ as the sum of latencies in A if we place $$$i$$$ servers there, similarly for $$$DP_B$$$ and $$$DP_{T}$$$.
To calculate $$$DP_{T}[i]$$$(which means the total latency given $$$i$$$ servers can be installed in $$$T = A-e-B$$$), notice that there are exactly three scearios:
where $$$size()$$$ means the number of houses requiring the internet.
Now we can do the calculation recursively.(Actually you will do it bottom up)
Editorial for E3:
TLDR: The DP array actually forms a convex hull, which is intuitive since the marginal benefit when you installing a new server is decreasing. Hence when calculating the transitions, the so-called Minkowski addition can be applied to accelerate.
Problem C2 can be solved using heap to store the indexes for each elements of a.
For each update, we update the heap and remove first invalids value of the heap (if the index is i, check if b[i]==value)
We also use counter or set to keep track of adjacents pair with increasing condition