http://www.codechef.com/viewsolution/3429768
Why it got wrong?
Isn’t it a minimum spanning tree problem? If so, can we solve it using kruskal or prim algo.
can anyone explain me where is integer overflowing in my code ?
http://www.codechef.com/viewplaintext/3426847
Can kruskal’s and prim algorithm be used ?
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 .
please explain the case n=1…why isn’t the ans=0 for that?
what is the answer if input:
1
2
5 5
why can’t we use long n, long vector and long long sum??
long is 32 bit. You are getting integer overflow in your code.
2 Likes
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…
it is sum+=a[i]*min;
try
1
3
1000000 1000000 1000000
i got it. thanks ! 
Y cant kruskal be used ?
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.
No need to use tree or graph…
A simple solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int T,N;
cin>>T;
while(T–)
{
cin>>N;
long long int arr[N];
for(long long int i=0;i<N;i++)
{
cin>>arr[i];
}
sort(arr,arr+N);
long long int sum=0;
for(long long int i=1;i<N;i++)
{
sum+=arr[i]*arr[0];
}
cout<<sum<<endl;
}
}
1 Like
Why no one has mentioned the graph would be STAR? Such an easy problem!!!
answer would be 25
Why am I getting WA?
int solve(vector<i64> const& cities) noexcept {
i64 const min = *min_element(cities.begin(), cities.end());
i64 const sum = accumulate(cities.begin(), cities.end(), 0);
return min * (sum - min);
}