We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Jogging Cats
  5. Discussions

Jogging Cats

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 12 Discussions, By:

votes

Please Login in order to post a comment

  • racuna1
    1 year ago+ 0 comments

    Simple solution: DFS from each intersection (1 .. N) until recursion hits depth 4. When at depth, check if path to current node forms a cycle. Once a cycle is found, add it to a set if it is new (i.e., not isomorphic to discovered cycles). Size of the set is the solution.

    Code is left as an exercise for the reader. (Also my code is terrible.)

    1|
    Permalink
  • comp0zr
    1 year ago+ 1 comment

    In my opinion, the editorial's approach is unnecessarily complex. My approach is as follows:

    WARNING: SPOILERS AHEAD!

    • Store edges in standard adjacency lists for each node, and sort them.
    • Set mid = 1, iterate from 1 to V.
    • Iterate through mid's edges (call these nodes b).
    • Iterate through b's edges (call these nodes a).
    • Count the number of ordered a-b pairs strictly (a < b < mid) (since the adjacency lists are sorted, you can terminate each loop according to this logic).
    • After all edges have been checked, run through the set of counts. For each count, add count * (count - 1) / 2 to the result.
    • Return result.
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ULL;
    
    int V, E;
    vector<int> adj[50010];
    
    ULL Solve()
    {
        ULL res = 0;
            
        for(int mid = 1; mid <= V; mid++)
        {        
            map<int, int> counts;
            
            for(auto b : adj[mid])
            {                              
                if(b >= mid) break;
                  
                for(auto a : adj[b])
                {    
                    if(a >= mid) break;                      
                    
                    counts[a]++;                                
                }            
            }
            for(auto it : counts)
            {
                int start = it.first;
                int count = it.second;
                            
                res += (count * (count - 1)) / 2;            
            }
        }    
        return res;
    }
    
    int main() 
    {
        cin >> V >> E;
        
        for(int i = 0; i < E; i++)
        {
            int a, b;
            cin >> a >> b;
            
            if(a > b) swap(a, b);
                    
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i = 1; i <= V; i++)
        {
            sort(adj[i].begin(), adj[i].end());        
        }    
        cout << Solve() << "\n";
        
        return 0;
    }
    
        return 0;
    }
    
    0|
    Permalink
  • bigjuicer1337
    1 year ago+ 0 comments

    Cats sure do love jogging, mine goes for a walk for a couple of hours every day. If your cat is often feeling tired, I recommend talking to UK Pet Drugs consultants. They will help you determine if your pet is having any health conditions and quickly find necessary medications to order.

    0|
    Permalink
  • erdenesukh
    4 years ago+ 0 comments

    there are 6 different roads and in the description it says 3, wow HACKERRANK challenges are really poorly written, i have been coding for 4 days now and every single one of them have been written so poorly that trying to grasp what the hell the writer wants is way more complicated than the actual coding... coding - 5 mins, reading 10 mins and more... disappointed

    0|
    Permalink
  • kvnsmnsn
    5 years ago+ 2 comments

    That last post came out garbled. The six correct solutions are:

    1 (1 -> 2 -> 3 -> 4), #2 (1 -> 2 -> 4 -> 3), #3 (1 -> 3 -> 2 -> 4), #4 (1 -> 3 -> 4 -> 2), #5 (1 -> 4 -> 2 -> 3), and #6 (1 -> 4 -> 3 -> 2).

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature