diagon_alley's blog

Atcoder: NIKKEI Programming contest — Problem E
By diagon_alley, history, 6 years ago, In English

Hey Everyone, Can anyone tell how to solve the problem Weights on vertices and edges from atcoder recent contest. Editorial seems a way difficult to understand. If anyone solved that problem, pls help me. Thanks! I have started this thread to know other's idea about the problem.

  • Vote: I like it
  • +32
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

First let's consider a top-down solution. Let's look at the graph with all the edges added, and consider a single connected component. If the sum of weights of verticies in this component is not less than the maximum weight of an edge belonging to this component, then we do not need to remove any edges from that component at all. Otherwise, the edge with the maximum weight must be removed. We continue this process until all the connected components form a valid construction.

To efficiently implement the solution above, let's consider a bottom-up approach. Let's sort the edges in the increasing order and add them one by one to the graph. For each connected component we maintain the answer to the problem — the minimum number of edges needed to be removed from that component to get a valid construction ("number of bad edges"), and the sum of weights of all vertices in that component ("sum of weights").

What happens when we add a new edge?

  1. if the edge connects two vertices in the same component, we just check if the newly added edge is heavier than sum of weights in this component, and if it is indeed heavier, we increase the number of bad edges in the component by one (since in the current graph the newly added edge must be removed).

  2. if the edge connects two different components, we merge them, and again check if the newly added edge is heavier than sum of weights in this (merged) component. If it is indeed heavier, we just increase the number of bad edges by one. Otherwise, since the new edge is not a bad one, neither are all the bad edges in the two original components we merged — those edges are lighter because we consider the edges in the increasing order. In this case the new (merged) component has 0 bad edges.

The "merge" operation can be easily handled using DSU. At the end you need to sum the number of bad edges in each connected component.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks a lot!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks a lot for exhaustive explanation!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sir, if we join two components through an edge and if (weg[edge]>sum of all vertices of merged component) holds then this paricular edge is surely bad but there may be some edges in merged component which we are counting as bad even now instead they are not bad any more because of increased total sum of vertices, am i right? if i understood rightly we are always merging components . please help a bit.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Even though some bad edges will indeed have weight less than the total sum of weights of all vertices in the merged component, they are still bad (we need to remove them), because we have to remove the last edge (it's a bad one), and after removing the last one, we'll have two different smaller components again. Consider the following example:

      If we add the red edge, even though the old edges have now weight 3 < 4, we still need to remove them all.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh i completely overlooked it, thanks a lot for explaining:D

        → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

nice explanation.

→ Reply