We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My solution, in Javascript:
I've used a sorted list for the corridors, and then an "extract" method in order to get all the following corridors to a room using binary search. Then finding the distance from the first room (A) to all the other rooms in the maze. After that, a simple substraction to find all the queried distances: from-X-to-Y equals from-A-to-Y minus from-A-to-X.
Since all the rooms are connected (by definition of the problem), any loop found will affect all the distances the same. And the sum of loops equals the GDP between them. Finally the closest you can be to the MOD value is the residue of the difference between your found distance and the MOD value minus one applying the GDP between the maze loop and the given MOD.
functionlongestModPath(corridor,queries){constloopSet=(val)=>loop=GCD(loop,val)constroomSet=(x,val)=>{if(room[x]!=null)loopSet(room[x]-val);elseroomCount++;room[x]=val}constmapCorridor=(c,pos)=>({from:c[0],to:c[1],val:c[2],pos})constmapRodirroc=(c,pos)=>({from:c[1],to:c[0],val:-c[2],pos})constsortStack=(a,b)=>a.from-b.from||a.to-b.to||a.val-b.valconstGCD=(A,B)=>((x,y)=>{const_gcd=(a,b)=>{letg;while(b){g=a%b;a=b;b=g;}return(a)};return((y>x)?_gcd(y,x):_gcd(x,y))})(Math.abs(A),Math.abs(B))letloop,nextPileletstack=corridor.map(mapCorridor).concat(corridor.map(mapRodirroc)).sort(sortStack)letpile=extract(1,0,1)letroom=[null,0],roomCount=1// Here I solve all the mazedo{nextPile=[]pile.forEach(({from,to,val})=>{if(from==to)loopSet(val)else{roomSet(to,val+room[from])nextPile=nextPile.concat(extract(to))}})pile=nextPile}while(nextPile.length>0)// Here I calculate all the queried resultsqueries.forEach((q,i,a)=>{letm=q[0],n=q[1],mod=q[2],val,resp,looper=GCD(loop,mod)if(mod<=1)resp=0elseif(looper==1)resp=mod-1else{val=(m==n)?0:(room[n]-room[m])%looperresp=(mod-1)-(mod-1-val)%looper}a[i]=resp})returnqueries//Binary search function to get all corridors starting at "where"functionextract(where,start=0,end=null){if((end==null)||(end>=stack.length))end=stack.length-1if(start<0)start=0while(start<end){letmid=Math.floor((start+end)/2)lettest=stack[mid]if(test.from==where){letini=mid,fin=mid,resp=[]if(corridor[test.pos]){resp.push(test)corridor[test.pos]=null}while((--ini>=0)&&(test=stack[ini]).from==where){if(corridor[test.pos]){resp.push(test)corridor[test.pos]=null}}while((++fin<stack.length)&&(test=stack[fin]).from==where){if(corridor[test.pos]){resp.push(test)corridor[test.pos]=null}}returnresp}elseif(where<test.from)end=mid-1elsestart=mid+1}return[]}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Longest Mod Path
You are viewing a single comment's thread. Return to all comments →
My solution, in Javascript: I've used a sorted list for the corridors, and then an "extract" method in order to get all the following corridors to a room using binary search. Then finding the distance from the first room (A) to all the other rooms in the maze. After that, a simple substraction to find all the queried distances: from-X-to-Y equals from-A-to-Y minus from-A-to-X. Since all the rooms are connected (by definition of the problem), any loop found will affect all the distances the same. And the sum of loops equals the GDP between them. Finally the closest you can be to the MOD value is the residue of the difference between your found distance and the MOD value minus one applying the GDP between the maze loop and the given MOD.