HackerRank Jogging Cats problem solution

In this HackerRank Jogging Cats problem solution 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?

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

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}