Can't understand solution

Can any body help me understand the solution of this . I saw the approaches taken by other contestants but I am unable to understand why such simple approach worked.

Hi, I solved this problem in the contest. So I hope I can help you. See in the question two people are bet against each other, now in order for Silol to be in profit he should give money to the guy taking less money,(as now if this guy backs out then the other will automatically back out). This can be applied for each pair.

My code

2 Likes

The best way to delete all n nodes is deleting them in decreasing order of their value.

Proof:

Consider each edge (x, y), it will contribute to the total cost v(x) or v(y) when it is deleted.

If we delete the vertices in decreasing order, then it will contribute only min(v(x), v(y)), so the total costs is the lowest.

So,one of the direct solution is : for each edge(x,y) , ans+=min(v(x),v(y)).

2 Likes

Thanks for your reply.