CHEFGAME - Editorial

editorial
, , , , ,
41

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.

42

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…:slight_smile:

43

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.
Please read the editorial carefully (the bold sentence).

1 Like
44

Thanks a lot…will keep in mind next time.

45

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.

46

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

47

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.

48

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)

49

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

50

Read editorial. Your mistakes are mentioned there.

1 Like
51

When maksi becomes zero you should break from the cycle.

1 Like
52

Well of course :smiley: Thanks Anton!

53

Thank you.
AC :slight_smile:

54

I would really appreciate someone looking at the solution

55

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

56

I got AC using Kruskal.
Here’s my code link: https://www.codechef.com/viewsolution/24909987

57

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

58

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 adj[7000];
vector dim[7000];
bool marked[7000];

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++)
    {
        y = adj[x][i].first;
        
        if(marked[y] == false)
        {
            Q.push(adj[x][i]);
        }
    }
}
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);
            adj[i].pb(make_pair(j, dist));
            adj[j].pb(make_pair(i, dist));
            dist = 0;
        }
    }
    
    cout << prim(0) << endl;
    
}

return 0;

}