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.

Check this:

Closure problem

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. :|

Question 1:

The

s-tmin-cut can be interpreted as the lowest weight sum of all the edges we need to remove so that there is no path fromstot.We will never remove an edge that has infinity weight (the "condition" edge). So, if we need to remove an edge from

sto an objectiwith weightw_{ i}> 0 ("bonus" object), that mean we cannot choose objectiand lose that bonus. If we need to remove an edge from an objectiwith weightw_{ i}< 0 ("penalty" object) tot, that mean we will have to choose objectiand 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

minimizethe 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

ithen we must also smash label that are multiple of it, add the following conditions for the closure problem:i- >j(jis a multiple ofiandj>i), which is equivalent to edge (i,j, + ∞) in the flow.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!