HackerRank Walking the Approximate Longest Path problem solution

YASH PAL,

In this HackerRank Walking the Approximate Longest Path problem solution Jenna is playing a computer game involving a large map with N cities numbered sequentially from 1 to N that are connected by M bidirectional roads. The game’s objective is to travel to as many cities as possible without visiting any city more than once. The more cities the player visits, the more points they earn.

As Jenna’s fellow student at Hackerland University, she asks you for help choosing an optimal path. Given the map, can you help her find a path that maximizes her score?

HackerRank Walking the Approximate Longest Path problem solution

Problem solution in Python.

# Enter your code here. Read input from STDIN. Print output to STDOUT
n,m=map(int,input().split())
roads=[]
dic={}
for i in range(m):
    [x,y]=list(map(int,input().split()))
    roads.append([x,y])
    if not x in dic:dic[x]={y}
    if x in dic:dic[x].add(y)
    if not y in dic:dic[y]={x}
    if y in dic:dic[y].add(x)
count=[0]*(n+1)
for x in dic:
    count[x]=len(dic[x])
_,start=min([[count[z],z] for z in dic],key=lambda a:a[0])
path=[start]
x=start
for i in range(1,n):
    if len(dic[x])==0:break
    _,y=min([[count[z],z] for z in dic[x]],key=lambda a:a[0])
    if x in dic[y]: dic[y].remove(x)
    count[y]-=1
    path.append(y)
    x=y
        
print(len(path))
print(*path, sep=" ")

Problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int n1=0;
        int n2=0;
        ArrayList<ArrayList<Integer>> nodeConn = new ArrayList<ArrayList<Integer>>();
        int[] nodeLen = new int[n];
        for (int i=0; i<n; i++){
            nodeConn.add(new ArrayList<Integer>());
        }
        for (int i=0; i<m; i++){
            n1 = in.nextInt()-1;
            n2 = in.nextInt()-1;
            nodeConn.get(n1).add(n2);
            nodeLen[n1]++;
            nodeConn.get(n2).add(n1);
            nodeLen[n2]++;
        }
        int min=0;
        for (int i=0; i<n; i++){
            //System.out.print((i+1) + " "+ nodeLen[i]+" ");
            if(nodeLen[i]<nodeLen[min])
                min=i;
            //System.out.println(min+1);
        }
        ArrayList<Integer> temp = new ArrayList<Integer>();
        int currNode = 0;
        int newMin = 0;
        int count = 0;
        int[] path = new int[n];
        while(nodeLen[min]!=0&&count<=n){
            path[count]=min+1;
            temp = nodeConn.get(min);
            newMin=temp.get(0);
            for(int i=0; i<temp.size(); i++){
                currNode = temp.get(i);
                nodeConn.get(currNode).remove((Integer)min);
                nodeLen[currNode]--;
                if(nodeLen[currNode]<nodeLen[newMin])
                    newMin=currNode;
            }
            min = newMin;
            count++;
        }
        if(count!=n){
            path[count]=min+1;
            count++;
        }
        System.out.println(count);
        for (int i=0; i<count; i++){
            System.out.print(path[i] + " ");
        }
    }
}

Problem solution in C++.

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=10000+10,maxm=100000+10;
int ans[maxn],d[maxn],now[maxn],a[maxn],b[maxn],c[maxn];
int h[maxn],go[maxm*2],nex[maxm*2];
bool bz[maxn];
int i,j,k,w,l,t,n,m,tot,ca;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int random(int x){
    int t=rand()%10000;
    t=t*10000+rand()%10000;
    return t%x;
}
void add(int x,int y){
    d[y]++;
    go[++tot]=y;
    nex[tot]=h[x];
    h[x]=tot;
}
int main(){
    n=read();m=read();
    fo(i,1,m){
        j=read();k=read();
        add(j,k);add(k,j);
    }
    ca=800;
    while (ca--){
        fo(i,1,n) now[i]=d[i],bz[i]=0;
        k=random(n)+1;
        w=k;
        a[a[0]=1]=k;
        bz[k]=1;
        while (1){
            c[0]=0;
            j=0;
            t=h[k];
            while (t){
                now[go[t]]--;
                if (now[go[t]]==1&&!bz[go[t]]) j=go[t];
                if (!bz[go[t]]) c[++c[0]]=go[t];
                t=nex[t];
            }
            if (!c[0]) break;
            if (!j) j=c[random(c[0])+1];
            bz[j]=1;
            a[++a[0]]=j;
            k=j;
        }
        k=w;
        b[b[0]=1]=k;
        while (1){
            c[0]=0;
            j=0;
            t=h[k];
            while (t){
                if (k!=w) now[go[t]]--;
                if (now[go[t]]==1&&!bz[go[t]]) j=go[t];
                if (!bz[go[t]]) c[++c[0]]=go[t];
                t=nex[t];
            }
            if (!c[0]) break;
            if (!j) j=c[random(c[0])+1];
            bz[j]=1;
            b[++b[0]]=j;
            k=j;
        }
        if (a[0]+b[0]-1>ans[0]){
            ans[0]=a[0]+b[0]-1;
            fd(i,a[0],1) ans[a[0]-i+1]=a[i];
            fo(i,2,b[0]) ans[a[0]+i-1]=b[i];
        }
    }
    printf("%dn",ans[0]);
    fo(i,1,ans[0]) printf("%d ",ans[i]);
    printf("n");
}

Algorithms coding problems solutions