 # CHEFGAME - Editorial

Complexity of your solution is O(N^2 * log N).
It is slow in this problem.
Refer to code snippet in editorial.
It contains simple O(N^2) solution without any data structures.

Firstly thanks for the reply,secondly could you please explain me how did you come up with that complexity…actually I thought that my complexity is O(N*log N)…considering the log N was the insertion time in the priority queue…Thanks in advance again… At each step of algorithm (N-1 times) for each unvisited vertex you push pair (u, j) to the heap.
So total number of pushes is about N*N/2.
Also you should not take distance modulo MOD when create adjacency matrix.

1 Like

Thanks a lot…will keep in mind next time.

`k+=(a*a)` should be `k += (long long)a * a`
`sum=(sum*k)%MOD` should be `sum = k%MOD * sum % MOD`
But most likely after this it will get TLE.

thank you very very much for your help i made the changes and it worked…got ac after 10 wa

Congrats!
You were lucky to pass with O(N^2 * log N) solution which supposed to get TLE in this problem.
This is probably because of own-written heap class.

can you explain how the complexity comes out to be O(N^2 * log N) .as in the while loop i build the heap which is o(n)and this loop will occur n times so overall complexity should be O(n^2)

Your solution is quite unclear. But it seems to me that `maxheapify` has complexity O(log(n/i)) in the worst case. And `build` call it for all i from 1 to n/2. So build has complexity O(n * log n).

1 Like

When `maksi` becomes zero you should break from the cycle.

1 Like

Well of course Thanks Anton!

Thank you.
AC I would really appreciate someone looking at the solution

When two towns have the same point, it’ll not connect those towns and give the initial answer which is 1.

I got AC using Kruskal.

I used kruskal and got ac in 3.91 sec…link to my solution
https://www.codechef.com/viewsolution/29236419

I have used Prim’s Algo with priority queue.Why is it giving TLE?

#include <bits/stdc++.h>
#include
#define lli long long int
#define mod 747474747
#define pb push_back
#define pp pop_back
#include
#include
#include <math.h>
#include <unordered_map>
using namespace std;

typedef pair<lli, lli> pi;

vector dim;
bool marked;

lli prim(lli x)
{
priority_queue<pi, vector> Q;
lli maxCost = 1, cost = 0;

``````Q.push(make_pair(x, 1));

while(!Q.empty())
{
pi f = Q.top();
Q.pop();
lli y = f.second, x = f.first;

if(marked[x])
{
continue;
}
//maxCost = (maxCost*y)%mod;
//cost += y;
maxCost = (maxCost*y)%mod;
maxCost %= mod;
marked[x] = 1;

for(lli i = 0; i < adj[x].size(); i++)
{

if(marked[y] == false)
{
}
}
}
return maxCost%mod;
``````

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

``````lli t;
cin >> t;

while(t--){

//memset(marked, 0, sizeof(marked));

lli n, d, x;
cin >> n >> d;

for(lli i = 0; i < n; i++)
{
for(lli j = 0; j < d; j++)
{
cin >> x;
dim[i].pb(x);
}
}

lli dist = 0;

for(lli i = 0; i < n-1; i++)
{
for(lli j = i+1; j < n; j++)
{
for(lli k = 0; k < d; k++)
{
dist += pow((dim[i][k] - dim[j][k]), 2);
//dist += fmod((pow(fmod((fmod(dim[i][k] - dim[j][k]), mod) + mod), mod), 2), mod);
}
//dist = fmod(pow(dist, 1/2), mod);