ENIGMA04 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

The Unhealthy Trick

Author and Editorialist: Ganesh Sawhney

DIFFICULTY:

Easy

PREREQUISITES:

Maths , sortings

PROBLEM:

The robot consists of n parts and m wires. Each wire links two parts, but every pair of parts is linked by at most one wire.
To destroy the robot, we have to remove all parts.
One part can be removed at 1 time and each remove consume some time. Let’s define a time value of part i as ti.
Time required to remove a part (let be x) is equal to the Sum of time values of all the parts directly connected by a wire to x. We need to find the minimum total time.

QUICK EXPLANATION:

Let for a particular wire, part “x” any “y” are connected. Take the minimum time value out of both and sum the values so obtained for all wires.

EXPLANATION:

The best way to delete all n nodes(remove all n parts) is deleting them in decreasing order of their value(time required).

Proof:
Consider each edge(wire) (x, y), it will contribute to the total time tx or  ty when it is deleted.
If we delete the vertices in decreasing order, then it will contribute only min(tx, ty), so the total costs(time) is the lowest.

SOLUTION:

Solution 1

Solution 2