You are not logged in. Please login at www.codechef.com to post your questions!

×

ENIGMA04 - Editorial

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

This question is marked "community wiki".

asked 16 Oct '15, 22:37

sumit.asr_128's gravatar image

2★sumit.asr_128
464
accept rate: 10%

edited 17 Oct '15, 04:52

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×3,746
×1,000
×877
×785
×42

question asked: 16 Oct '15, 22:37

question was seen: 769 times

last updated: 17 Oct '15, 04:52