HackerRank Jogging Cats Problem Solution

In this post, we will solve HackerRank Jogging Cats Problem Solution.

It’s almost summertime, so Big Cat and Little Cat are getting in shape. They decide the core of their fitness plan is to start jogging every day.
Their city consists of N Intersections connected by M bidirectional roads. The cats decide that their jogging route should be cyclic (i.e., starting and ending at the same intersection) and consist of 4 different roads.
The cats also love exploring new places, so each day they want to choose a new route to jog on that is not equal to any of their previous routes. Two routes are considered to be equal if their sets of component roads are equal.
Given a map of the city, can you help our heroic cats determine the maximum number of days they can go jogging so that every route traveled is different?
Input Format
The first line contains a pair of space-separated integers, N (the number of intersections) and M (the number of roads), respectively.
Each line of the M subsequent lines contains a pair of space-separated integers, X, and Yi, defining a bidirectional road connecting intersections Xi and Yi.

Output Format

Print the maximum number of days for which the cats can go jogging without repeating a route.

Sample Input

Sample Output

Explanation
There are 3 different routes:
1.1→ 2→ 3 →4→1
2.1→ 3→ 2→4→1
3.1→ 2→ 4→ 3→1
Recall that each route is a set of intersections forming a cycle, so each unique route is the same regardless of which city on the route the cats start out at. Thus, we print 3 (the number of routes) as our answer.

Table of Contents

Jogging Cats C Solution

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

struct edge{
    int from;
    int to;
};

bool precedge(struct edge e1, struct edge e2){
    return e1.from < e2.from || (e1.from == e2.from && e1.to < e2.to);
}

void setup(int n, int m, int** edges, struct edge *sortedge, int* edgebds){
    for(int i = 0; i < m; i++){
        sortedge[2*i].from = edges[i][0] - 1;
        sortedge[2*i].to = edges[i][1] - 1;
        sortedge[2*i + 1].from = edges[i][1] - 1;
        sortedge[2*i + 1].to = edges[i][0] - 1;
    }

    for(int i = 0; i < 2*m; i++){
        int curr = i;
        while(curr > 0){
            int next = (curr - 1)/2;
            if(precedge(sortedge[next], sortedge[curr])){
                struct edge temp = sortedge[curr];
                sortedge[curr] = sortedge[next];
                sortedge[next] = temp;
                curr = next;
            }
            else{
                break;
            }
        }
    }

    for(int i = 2*m - 1; i >= 0; i--){
        struct edge temp = sortedge[0];
        sortedge[0] = sortedge[i];
        sortedge[i] = temp;

        int curr = 0;
        while(true){
            int next = curr;
            if(2*curr + 1 < i && precedge(sortedge[next], sortedge[2*curr + 1])){
                next = 2*curr + 1;
            }
            if(2*curr + 2 < i && precedge(sortedge[next], sortedge[2*curr + 2])){
                next = 2*curr + 2;
            }
            if(next != curr){
                struct edge temp = sortedge[curr];
                sortedge[curr] = sortedge[next];
                sortedge[next] = temp;
                curr = next;
            }
            else{
                break;
            }
        }
    }

    edgebds[0] = 0;
    for(int i = 0; i < n; i++){
        int index = edgebds[i];
        while(index < 2*m && sortedge[index].from == i){
            index++;
        }
        edgebds[i + 1] = index;
    }
}

long jogroutes(int n, int m, int** edges){
    struct edge sortedge[2*m];
    int edgebounds[n + 1];
    setup(n, m, edges, sortedge, edgebounds);
    long toreturn = 0;
    for(int i = 0; i < n; i++){
        int start = edgebounds[i];
        for(; start < edgebounds[i + 1] && sortedge[start].to < i; start++);
        
        int numneighbors = edgebounds[i + 1] - start;
        if(numneighbors > 50){
            for(int j = i + 1; j < n; j++){
                if(edgebounds[j] + 1 < edgebounds[j + 1]){
                    long common = 0;
                    int index1 = start;
                    int index2 = edgebounds[j];
                    while(index1 < edgebounds[i + 1] && index2 < edgebounds[j + 1]){
                        if(sortedge[index1].to == sortedge[index2].to){
                            common++;
                            index1++;
                            index2++;
                        }
                        else if(sortedge[index1].to > sortedge[index2].to){
                            index2++;
                        }
                        else{
                            index1++;
                        }
                    }
                    toreturn += common*(common - 1);
                }
            }
        }
        else{
            for(int j = start; j < edgebounds[i + 1]; j++){
                int node1 = sortedge[j].to;
                int nextstart = edgebounds[node1];
                for(; nextstart < edgebounds[node1 + 1] && sortedge[nextstart].to <= i; nextstart++);
                for(int k = j + 1; k < edgebounds[i + 1]; k++){
                    int node2 = sortedge[k].to;
                    int index1 = nextstart;
                    int index2 = edgebounds[node2];
                    while (index1 < edgebounds[node1 + 1] && index2 < edgebounds[node2 + 1]){
                        if(sortedge[index1].to == sortedge[index2].to){
                            toreturn += 2;
                            index1++;
                            index2++;
                        }
                        else if(sortedge[index1].to > sortedge[index2].to){
                            index2++;
                        }
                        else{
                            index1++;
                        }
                    }
                }
            }
        }
    }
    return toreturn/2;
}

int main() {
    int n, m;
    scanf("%d %d\n", &n, &m);
    int** edges = malloc(m*sizeof(int*));
    for(int i = 0; i < m; i++){
        edges[i] = malloc(2*sizeof(int));
        scanf("%d %d\n", edges[i], edges[i] + 1);
    }
    long result = jogroutes(n, m, edges);
    printf("%ld", result);
    return 0;
}



char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

Jogging Cats C++ Solution

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
#include <set>

using namespace std;

const int MAXN = 50000 + 10;

vector<int> adj[MAXN], adj_big[MAXN];
int n, m, ans[5], wn, w[MAXN], x, y;
int am[MAXN][MAXN / 30 + 10];
long long ans4;

inline bool exists_edge (int x, int y) {
    return ((am[x][y / 30] & (1 << (y % 30))) > 0);
}

const int MAX_BIG_NODES = 4000;

int p[MAX_BIG_NODES][MAX_BIG_NODES], big_index[MAXN], big_nodes, q[MAX_BIG_NODES][MAX_BIG_NODES];

void count_4cliques () {
    int threshold = (int)exp(log(n * 1.0) / 3.0);
    for(int i = 1; i <= n; i++) if (adj[i].size() >= threshold) 
        big_index[i] = ++big_nodes;
    for(int i = 1; i <= n; i++) for(int j = 0; j < adj[i].size(); j++) {
        if (big_index[adj[i][j]])
            adj_big[i].push_back(adj[i][j]);
    }
    // 4 big nodes    
    long long ans_4big = 0;
    for(int i = 1; i <= n; i++) if (big_index[i]) for(int j = 0; j < adj_big[i].size(); j++) {
        int x = big_index[i];
        int xy = adj_big[i][j];
        for(int k = 0; k < adj_big[xy].size(); k++) {
            int z = big_index[adj_big[xy][k]];
            if (z && z != x)
                ans_4big += p[x][z]++;
        }
    }
    // 3 big nodes
    long long ans_3big = 0;
    for(int i = 1; i <= n; i++) if (!big_index[i]) {
        for(int j = 0; j < adj_big[i].size(); j++) {
            int x = big_index[adj_big[i][j]];
            for(int k = j + 1; k < adj_big[i].size(); k++) {
                int y = big_index[adj_big[i][k]];
                ans_3big += p[x][y];
            }
        }
    }
    // 2 big nodes lie diagonally
    long long ans_2big_diagonal = 0;
    for(int i = 1; i <= n; i++) if (!big_index[i]) {
        for(int j = 0; j < adj_big[i].size(); j++) {
            int x = big_index[adj_big[i][j]];
            for(int k = j + 1; k < adj_big[i].size(); k++) {
                int y = big_index[adj_big[i][k]];
                ans_2big_diagonal += q[min(x, y)][max(x, y)]++;
            }
        }        
    }
    // 2 big nodes are connected
    long long ans_2big_conn = 0;
    for(int i = 1; i <= n; i++) if (!big_index[i]) {
        for(int j = 0; j < adj[i].size(); j++) if (!big_index[adj[i][j]]) {
            int y = adj[i][j];
            for(int a = 0; a < adj_big[i].size(); a++) 
                for(int b = 0; b < adj_big[y].size(); b++) {
                    int qa = adj_big[i][a];
                    int qb = adj_big[y][b];
                    ans_2big_conn += exists_edge(qa, qb);
                }
        }
    }
    // 1 big node OR 0 big nodes
    long long ans_1big = 0;
    long long ans_0big = 0;
    for(int i = 1; i <= n; i++) if (!big_index[i]) {
        for(int j = 0; j < adj[i].size(); j++) if (!big_index[adj[i][j]]) {
            int x = adj[i][j];
            for(int k = j + 1; k < adj[i].size(); k++) if (!big_index[adj[i][k]]) {
                int y = adj[i][k];
                for(int l = 0; l < adj[x].size(); l++) if (big_index[adj[x][l]] && adj[x][l] != i && adj[x][l] != y) 
                    ans_1big += exists_edge(adj[x][l], y);
                else if (adj[x][l] != i) 
                    ans_0big += exists_edge(adj[x][l], y);
            }
        }
    }
    ans4 = ans_4big / 4 + ans_3big + ans_2big_conn / 2 + ans_2big_diagonal + ans_1big + ans_0big / 4;
}

int main () {    
    set<pair<int, int> > edges;
    cin >> n >> m;
    assert(1 <= n && n <= 50000);
    assert(1 <= m && m <= 100000);
    for(int i = 1; i <= m; i++) {
        cin >> x >> y;
        assert(1 <= x && x <= n);
        assert(1 <= y && y <= n);
        assert(x != y);
        edges.insert(make_pair(min(x, y), max(x, y)));
        am[x][y / 30] |= (1 << (y % 30));
        am[y][x / 30] |= (1 << (x % 30));
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    assert(edges.size() == m);
    count_4cliques();
    cout << ans4 << endl;
    return 0;
}

Jogging Cats C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        var tmp = Console.ReadLine().Split(' ');
        int n = int.Parse(tmp[0]), m = int.Parse(tmp[1]),l,r;

        var adj = new List<int>[n];
        for (int i = 0; i < n; i++) adj[i] = new List<int>();

        for (int i = 0; i < m; i++) {
            tmp = Console.ReadLine().Split(' ');
            l = int.Parse(tmp[0]) - 1;
            r = int.Parse(tmp[1]) - 1;
            adj[l].Add(r); adj[r].Add(l);
        }
        for (int i = 0; i < n; i++) adj[i].Sort();

        Dictionary<long, long> map = new Dictionary<long, long>();

        for (int i = 0; i < n; i++) {
            long tt = Math.BigMul(i, 1000000);
            adj[i].ForEach(mid => {
                if (mid > i) {
                    var ad = adj[mid];
                    int j = ad.BinarySearch(i) + 1;
                    for (; j < ad.Count; j++) {
                        update(map, tt + ad[j]);
                    }
                }
            });
        }

        Console.WriteLine(map.Values.Sum(x => x * (x - 1)) / 2);
    }
    static void update(Dictionary<long, long> map, long k) {
        if (map.ContainsKey(k)) map[k]++; else map[k] = 1;
    }
}

Jogging Cats Java Solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = 150;
        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Integer>[] edgesList = new ArrayList[n];

        for (int i = 0; i < n; ++i) {
            edgesList[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            edgesList[u].add(v);
            edgesList[v].add(u);
        }

        int[][] edges = new int[n][];
        for (int i = 0; i < n; ++i) {
            edges[i] = new int[edgesList[i].size()];
            for (int it = 0; it < edges[i].length; ++it) {
                edges[i][it] = edgesList[i].get(it);
            }
            Arrays.sort(edges[i]);
        }
        long[] ar = new long[m * K];
        int arLen = 0;
        long ans = 0;
        boolean[] col = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (edges[i].length <= K) {
                for (int it = 0; it < edges[i].length; ++it) {
                    for (int jt = it + 1; jt < edges[i].length; ++jt) {
                        ar[arLen++] = n * edges[i][it] + edges[i][jt];
                    }
                }
            } else {
                Arrays.fill(col, false);
                for (int j : edges[i]) {
                    col[j] = true;
                }
                for (int j = 0; j < n; ++j) {
                    if (edges[j].length > K && j <= i) {
                        continue;
                    }
                    long cnt = 0;
                    for (int k : edges[j]) {
                        if (col[k]) {
                            cnt++;
                        }
                    }
                    ans += cnt * (cnt - 1) / 2;
                }
            }
        }
        Arrays.sort(ar, 0, arLen);
        for (int i = 0; i < arLen; ) {
            int j = i;
            while (j < ar.length && ar[i] == ar[j]) {
                ++j;
            }
            long cnt = j - i;
            ans += cnt * (cnt - 1) / 2;
            i = j;
        }
        if (ans % 2 != 0) {
            throw new AssertionError();
        }
        System.out.println(ans/2);
    }
}

Jogging Cats Python Solution

# Enter your code here. Read input from STDIN. Print output to STDOUT
def joggingCats(n,m,graph):
    result = 0
    visited = set([])
    for source,destinations in graph.items():
        destinationCount = {}
        for x in destinations:
            if x not in visited and x in graph:
                for y in graph[x]:
                    if y not in visited:
                        try:
                            destinationCount[y] += 1
                        except:
                            destinationCount[y] = 1
        for node,count in destinationCount.items():
            if node != source:
                result+= count*(count-1)//2
        visited.add(source)
    return result


if __name__ == '__main__':

    n,m =  [int(i) for i in input().strip().split()]
    graph = {}
    for _ in range(m):
        x,y = [int(i) for i in input().strip().split()]
        try:
            graph[x].append(y)
        except:
            graph[x] = [y]
        try:
            graph[y].append(x)
        except:
            graph[y] = [x]
    print(joggingCats(n,m,graph))

Jogging Cats C Solution

Jogging Cats C++ Solution

Jogging Cats C Sharp Solution

Jogging Cats Java Solution

Jogging Cats Python Solution

Related Posts