HackerRank Jogging Cats problem solution

In this 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?

HackerRank Jogging Cats problem solution in Java.

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 problem solution in C++.

#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;
}

Problem solution in C.

#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 %dn", &n, &m);
    int** edges = malloc(m*sizeof(int*));
    for(int i = 0; i < m; i++){
        edges[i] = malloc(2*sizeof(int));
        scanf("%d %dn", 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] = '';
    }

    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;
}