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

×

KINGSHIP - Editorial

7
2

PROBLEM LINK:

Practice
Contest

Author: Shiplu Hawlader
Tester: Tasnim Imran Sunny
Editorialist: Lalit Kundu

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Connected Graph
Tree

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.

image2

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.

image3

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

asked 17 Feb '14, 00:14

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%

edited 17 Feb '14, 09:31

garakchy's gravatar image

1★garakchy
1.1k163048

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

(17 Feb '14, 00:28) kuldeep9922★

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

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

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

@kuldeep992: You should have used long to avoid integer overflow.

link

answered 17 Feb '14, 00:37

shiplu's gravatar image

2★shiplu
563
accept rate: 20%

edited 17 Feb '14, 00:38

link

answered 17 Feb '14, 03:05

palash1010's gravatar image

2★palash1010
1
accept rate: 0%

2

long is 32 bit. You are getting integer overflow in your code.

(17 Feb '14, 18:19) shiplu2★

Isn't it a minimum spanning tree problem? If so, can we solve it using kruskal or prim algo.

link

answered 18 Feb '14, 15:22

dragonemperor's gravatar image

3★dragonemperor
89321134
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) betlista ♦♦3★

Y cant kruskal be used ?

(18 Mar '14, 16:39) monel19942★

can anyone explain me where is integer overflowing in my code ? http://www.codechef.com/viewplaintext/3426847

link

answered 18 Feb '14, 16:46

anmolarora123's gravatar image

3★anmolarora123
10112
accept rate: 0%

it is sum+=a[i]*min;

try

1
3
1000000 1000000 1000000

http://ideone.com/B7AhUM

(18 Feb '14, 17:04) betlista ♦♦3★

i got it. thanks ! :)

(19 Feb '14, 22:32) anmolarora1233★

Can kruskal's and prim algorithm be used ?

link

answered 18 Mar '14, 16:39

monel1994's gravatar image

2★monel1994
1111
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) ashishtilokani5★

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 .

link

answered 14 Jan '16, 13:31

poorcoder's gravatar image

1★poorcoder
1
accept rate: 0%

please explain the case n=1...why isn't the ans=0 for that?

link

answered 11 Feb '16, 23:04

aru_674's gravatar image

2★aru_674
1
accept rate: 0%

what is the answer if input: 1 2 5 5

link

answered 10 May '17, 17:53

jpriya2903's gravatar image

2★jpriya2903
602
accept rate: 25%

why can't we use long n, long vector and long long sum??

link

answered 29 May '17, 16:35

umangahuja1's gravatar image

4★umangahuja1
202
accept rate: 0%

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,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