Codeforces Round #936 (Div. 2) Editorial

Codeforces Round #936 (Div. 2) Editorial

4 weeks ago, # | ← Rev. 2 →   +143 For C, why is there an entire paragraph discussing why rerooting doesn't affect the answer, but no discussion on why the greedy algorithm is optimal? BTW, I created video editorial for D: Birthday Gift.

4 weeks ago, # ^ | With fixed x you want to maximize number of edges to remove. Consider lowest subtree with >= x vertices, if we dont cut edge right up this subtree, we can move closest edge from top and answer won't get worse

• 4 weeks ago, # ^ | But when you when you disconnect a subtree with its parent, how do you make sure its parent's component still has more than x vertices? We are trying to make as many cuts as possible only considering the current subtree, but we do nothing to ensure the parent still has x or more. What am I missing?

  • 4 weeks ago, # ^ | ← Rev. 2 →   0 once there is a subtree with more than x points,you count it as a connected component and cut the connection with the subtree and it's father. it is shown that if the connected component which include the root maybe has x-less points.but it wasn't counted before.you just need to think it as add a edge which was cuttted before from this connected component to others.it won't affect the counting number.

    • 4 weeks ago, # ^ | ← Rev. 2 →   +1 so essentially, for a fixed x, and number of cuts k, you want k + 1 components whose size >= x. If you have 3 components, what's left of the chopped up parent can just be added to the components we just made

  • 4 weeks ago, # ^ | same doubt and also should we not have to check for k+1 connected components? as if we remove k edges , no. of connected components will be k+1 if i'm not wrong...

    • 2 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, but I think the idea is that when you're running the algorithm, you're not guaranteeing that the connected component containing the root node has size of at least x. So, if you remove k edges, you get k+1 connected components, but for one of them you can just connect it back to the component with the root node, giving you k connected components. That way it's unnecessary to check whether the component with the root node has size at least x.

  • 4 weeks ago, # ^ | we will remove the subtree sizes which we have cut already so that way will not count the removed subtree and after that we just check wether the component of which has root have the size greater that >= x its okay otherwise we have to make 1 less cut. you can check this, code for reference

    • 4 weeks ago, # ^ | ← Rev. 2 →   0 Why is there a need to decrease cnt if the root node has a size less than m? cnt is incremented only if we have gotten a size greater than m. So we never had an extra number in cnt. I do not understand the need to decrease it

      • 4 weeks ago, # ^ | Consider this case. n = 7, k = 3 1 2 2 3 1 4 4 5 1 6 6 7 To my understanding, the algorithm will cut edges (1, 2), (1, 4) and (1, 6). The cnt guarantees [0, cnt-1] cuts are possible, not exactly cnt cuts because it depends on the last group (root group) we made if its size >= particular x we are checking. You can try adding extra edge like (1, 8) and see what happens.

      • 4 weeks ago, # ^ | ← Rev. 3 →   0 root_comp_size < m all other comp size >= m so to make the root_comp also have size >= m , we can merge any adjacent other component to do that we need to remove 1 cut, which is what we did

  • 4 weeks ago, # ^ | I am just proving that it's optimal, like if we consider best way to choose edges, we can move edge lower, while subtree size is >= x. About algorithm of checking, of course we root a tree, then do this greedy, and we just need to check in the end that root component size is >= x, if not, then we can remove only 1 edge, cause all other comps are of size >= x

  • 4 weeks ago, # ^ | Just noting down my understanding if anyone is still confused about this: There are really only two cases to think about If the root component has at least x vertices If the root component has less than x vertices In the first case, it is straight forward. We simply have to check if we have at least k + 1 components, since making k cuts would lead to k + 1 components. In the second case, it is a bit of a think. As per most implementations, if we have less than x vertices, we have not added this component to our count of components yet. So we must increment this count by 1. But since we have less than x vertices, we also want to re-unite this component with another (that already has at least x vertices, which is why it had gotten disconnected in the first place). So we must also decrement the component count by 1. So ultimately, our component count remains the same, and we simply want to check if we have at least k + 1 components, for the same reason that making k cuts would lead to k + 1 components. Ref [C++ clean]: https://codeforces.com/contest/1946/submission/252842752