Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

mochow's blog

AtCoder Regular Contest 085 Problem E

By mochow, history, 7 years ago, In English

Can anyone explain the intuition behind the min-cut solution of the problem of the last ARC problem E? The editorial explains it but it does not explain the meaning of the taken steps.

The solution is quite fascinating but I cannot wrap my head around the complete idea.

Thanks in advance.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this:

Closure problem

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Okay I see the connection.

    One quick question to clear my confusion. When we take an edge in the min-cut, I mean when we take its weight summed up to the min-cut, what does this mean? What I see is that if the taken weight is from S group, then it means we are taking this value (not smashing it) and if it is from T group, it seems that we are smashing it as initially all positive valued elements were taken as a solution. Am I right?

    And then, if we smash a particular label, we need to smash all the other labels that are multiple of it. How is that ensured in the solution?

    Sorry for actually long question. :|

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

      Question 1:

      The s - t min-cut can be interpreted as the lowest weight sum of all the edges we need to remove so that there is no path from s to t.

      We will never remove an edge that has infinity weight (the "condition" edge). So, if we need to remove an edge from s to an object i with weight wi > 0 ("bonus" object), that mean we cannot choose object i and lose that bonus. If we need to remove an edge from an object i with weight wi < 0 ("penalty" object) to t, that mean we will have to choose object i and suffer the penalty. So, the weight of the min-cut is also the minimum lost compared to when we can just take all the bonus object without worrying about the condition.

      Please note that the closure problem in the article above is the maximum closure. The closure problem in ARC085 — E is the minimum closure (since we need to minimize the sum of the diamond set that will be removed), which can be changed into the maximum closure problem by negating all the diamond's value.

      Question 2:

      In other to ensure that if we smash label i then we must also smash label that are multiple of it, add the following conditions for the closure problem: i -  > j (j is a multiple of i and j > i), which is equivalent to edge (i, j,  + ∞) in the flow.

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

        I was trying this problem in the contest time. Then reading the editorial confused me in one particular point. If we lose a bonus, don't we lose all the bonuses with labels multiple of the current label? But how are we removing them from the initially all bonus sum? Thanks in advance!

        → Reply