- Prepare
- Algorithms
- Graph Theory
- Jogging Cats
- Discussions

# Jogging Cats

# Jogging Cats

+ 0 comments https://zeroplusfour.com/jogging-cats-hackerrank-solution/

Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

+ 0 comments My cat is too lazy to run, she only likes to eat and take a nap after. I can't believe that I had the same lifestyle a few months ago. I'm glad I decided to change it, started going to the gym, and taking weight management supplements from this page. I managed to lose weight, and now I feel much better.

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

Sort 13 Discussions, By:

Please Login in order to post a comment