-2
\$\begingroup\$

I tried a Hackerrank problem and it gives me a successful message, it works fine for Hackerrank criteria.

The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID's. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.
For example, we have the following data on 2 pairs of astronauts, and 4 astronauts total, numbered 0 through 3.
1 2, 2 3
Astronauts by country are [0] and [1,2,3]. There are 3 pairs to choose from: [0,1], [0,2] and [0,3].

There I used a DFS method to check for the connected components and get the answer using the sum of the products of each disjoint elements (\$ab + ac + ad + bc + bd + cd = ab + (a+b)c + (a+b+c)d\$).

Although it passes all test cases in the Hackerrank platform as required for 10^5 nodes, it fails in time for graphs with more nodes (for 10^9) as it takes more than 1.5ms of time. Can I have some improvement here to work this for more nodes?. As I have already mentioned, this works perfectly for Hackerrank and it passed all. But for my knowledge I need to have some further improvements to work in linear time.

Here's my code.

#include <iostream>
#include <vector>

using namespace std;

#define For(i,a,n) for (int i=a; i<n; i++)
typedef vector<int> vi;

// returns no. of connected nodes to a given node
int connected(int node, vector<vi> &adj, bool visited[]){
    int count = 0;
    for(auto x: adj[node]){
        if(visited[x]) continue;
        visited[x] = true;
        count += connected(x, adj, visited) + 1;
    }
    return count;
}

void dfs(int nodes, vector<vi> &adj, bool visited[]){
    long long ans = 0;
    visited[nodes] = true;
    int current_sum = connected(nodes, adj, visited) + 1;

    while(nodes--){
        if(visited[nodes]) continue;
        visited[nodes] = true;
        int out = connected(nodes, adj, visited) + 1;
        ans += current_sum*out;
        current_sum += out;    
    }
    cout<< ans;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int a,b,edges,nodes;
    cin>>nodes>>edges;
    bool visited[nodes];
    fill(visited, visited + nodes, 0);
    vector<vi> adj(nodes);

    // adj[i] gives the directly connected nodes to i
    while(edges--){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(nodes-1, adj, visited);
    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review. Please include a complete description of the challenge as well. Links can rot. \$\endgroup\$ – Mast May 22 at 11:58
  • \$\begingroup\$ [the code presented] fails for graph with more nodes fails to provide the correct answer or fails to meet some hackerrank.com criterion? \$\endgroup\$ – greybeard May 22 at 22:16
  • \$\begingroup\$ It is fine if the code does not work for large graphs, if it works in principle and only fails because it runs out of time/ressources. In that case there are the time-limit-exceeded and memory-optimization tags, respectively. \$\endgroup\$ – Graipher May 23 at 8:21
  • \$\begingroup\$ You might also want to contact a moderator if you want to merge your two accounts (i.e. the one you used to ask the question and the one you use to edit it), because otherwise you will need to wait for approval for every edit you make. Just click the flag link under the question and use a custom "in need of moderator intervention" flag. \$\endgroup\$ – Graipher May 23 at 8:25
  • \$\begingroup\$ (Reputation should not be keeping you from commenting to a post of your own.) \$\endgroup\$ – greybeard May 23 at 10:29
1
\$\begingroup\$

It would be good to have some test graph to try the code, I've generated an overly simple graph (one edge per node, 7MB file generated) using the following Python script (output redirected to file):

nodes = 1000000
edges = nodes/2
print("{} {}".format(nodes, edges))
for i in range(1, nodes+1, 2):
   print("{} {}".format(i, i+1))

Additionally, in order to profile data in Visual Studio, I've done following changes:

  1. At the start of main(), I've redirected cin to read from input file (needed to automate profiling): std::ifstream in("graph.dat"); std::cin.rdbuf(in.rdbuf());
  2. To placate Visual Studio C++ compiler, I've changed the visited array to: bool *visited = new bool[nodes]; ... delete[] visited;

With these changes, profiler shows that 86.5% of CPU time is spent in basic_istream (mostly in _Lock/_Unlock buffer methods, could be MSVC specific), i.e. reading the data. dfs algorithm itself takes only 0.45% of CPU time! If the entire program run time is measured at the competition, the obvious place is to refactor the data input to something much faster, possibly using low-level APIs like scanf.

Perhaps the profiling results will be different on Linux, my general advice is to use profiler.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ See here for faster input: stackoverflow.com/questions/15036878/… \$\endgroup\$ – Adriatic May 28 at 19:49
  • \$\begingroup\$ How did you check each of these times. Is there a way to do this in Visual Studio Code? \$\endgroup\$ – rusiru thushara May 28 at 20:32
  • \$\begingroup\$ I don't use Visual Studio Code, but as far as I know it doesn't have a profile feature. You can install Visual Studio 2019 Community edition, it does feature profiler. Or if on Linux, use "perf". \$\endgroup\$ – Adriatic May 29 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.