×

KINGSHIP - Editorial

Tester: Tasnim Imran Sunny
Editorialist: Lalit Kundu

SIMPLE-EASY

PROBLEM:

Connect all the N(<=10^5) cities to make a connected graph in minimum cost. Cost of adding each edge is product of population of the two cities between whom edge is being added. All populations are given in the input.

QUICK EXPLANATION:

Graph formed finally should be a tree. We connect all the other nodes to the node with smallest population which results in minimum cost.

EXPLANATION:

We need to add edges such that all the cities become connected. Connected is defined as "it should be possible from any city to reach any other city by a sequence of edges".

There doesn't exist a graph which is connected and has less than (N-1) edges (which is known as a tree).
So we will be constructing a tree finally with (N-1) edges.
Suppose we create some random tree with (N-1) edges. Now I pick two nodes i and j where Pi and Pj both are not the minimum and remove that edge from there and connect nodes x and j, where Px is minimum.

I have a change of ( Px * Pj ) - ( Pi * Pj ) which is less than zero since Px < Pi.

So, we all nodes will be connected to the node with smallest value.
Pseudo Code:

n=input
value array=input
ans=0
for i=1 to N-1:
ans += value[i]*value[0]
print ans


AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

3.0k93163187
accept rate: 12%

1★garakchy
1.1k163048

can you tell me why i got wrong answer... http://www.codechef.com/viewsolution/3428578

(17 Feb '14, 00:28)

http://www.codechef.com/viewsolution/3427213

sme here!! can u tell d reson 4r it's faliure?

(17 Feb '14, 15:37) 2★

 1 @kuldeep992: You should have used long to avoid integer overflow. answered 17 Feb '14, 00:37 2★shiplu 56●3 accept rate: 20%
 0 http://www.codechef.com/viewsolution/3429768 Why it got wrong? answered 17 Feb '14, 03:05 1 accept rate: 0% 2 long is 32 bit. You are getting integer overflow in your code. (17 Feb '14, 18:19) shiplu2★
 0 Isn't it a minimum spanning tree problem? If so, can we solve it using kruskal or prim algo. answered 18 Feb '14, 15:22 893●2●11●34 accept rate: 10% I think you can user Prim's algorithm, because of it's implementation if you start from vertex with min Pi, but not Kruskal's... (18 Feb '14, 15:39) Y cant kruskal be used ? (18 Mar '14, 16:39)
 0 can anyone explain me where is integer overflowing in my code ? http://www.codechef.com/viewplaintext/3426847 answered 18 Feb '14, 16:46 10●1●1●2 accept rate: 0% it is sum+=a[i]*min; try 1 3 1000000 1000000 1000000  http://ideone.com/B7AhUM (18 Feb '14, 17:04) i got it. thanks ! :) (19 Feb '14, 22:32)
 0 Can kruskal's and prim algorithm be used ? answered 18 Mar '14, 16:39 1●1●1●1 accept rate: 0% Complexity of Kruskal's is O(ElogV), while of this algorithm is linear. I guess it might result in TLE. Morever this algorithm is very easy to implement unlike Kruskal. (21 Apr '14, 09:14)
 0 to avoid integer overflow use ' long long ' . I had got a WA while using 'int' . and the problem is of 'ad-hoc ' category which means you do not require to apply any special algorithm to get it solved . answered 14 Jan '16, 13:31 1 accept rate: 0%
 0 please explain the case n=1...why isn't the ans=0 for that? answered 11 Feb '16, 23:04 2★aru_674 1 accept rate: 0%
 0 what is the answer if input: 1 2 5 5 answered 10 May '17, 17:53 60●2 accept rate: 25%
 0 why can't we use long n, long vector and long long sum?? answered 29 May '17, 16:35 20●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,492
×1,197
×1,164
×921
×11
×5

question asked: 17 Feb '14, 00:14

question was seen: 5,290 times

last updated: 01 Jun '17, 17:59