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.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Longest Mod Path
  5. Discussions

Longest Mod Path

  • brunopaulsen
     + 0 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.

    function longestModPath(corridor, queries) {
    const loopSet = (val) => loop=GCD(loop, val)
    const roomSet = (x, val) => {if(room[x]!=null)loopSet(room[x]-val);else roomCount++;room[x]=val}
    const mapCorridor = (c,pos)=>({from:c[0],to:c[1],val:c[2],pos})
    const mapRodirroc = (c,pos)=>({from:c[1],to:c[0],val:-c[2],pos})
    const sortStack = (a,b)=>a.from-b.from||a.to-b.to||a.val-b.val
    const GCD = (A,B) => ((x,y)=>{const _gcd=(a,b)=>{let g;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))
    let loop, nextPile
    let stack=corridor.map(mapCorridor).concat(corridor.map(mapRodirroc)).sort(sortStack)
    let pile=extract(1,0,1)
    let room=[null,0], roomCount=1
// Here I solve all the maze
    do {
        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 results
    queries.forEach((q, i, a) =>{
        let m=q[0], n=q[1], mod=q[2], val, resp, looper = GCD(loop, mod)
        if (mod<=1) resp = 0
        else if (looper==1) resp = mod-1
        else {
            val = (m==n)?0:(room[n] - room[m])%looper
            resp = (mod - 1) - (mod - 1 - val) % looper
        }
        a[i] = resp
    })
    return queries
//Binary search function to get all corridors starting at "where"
    function extract(where, start = 0, end = null) {
        if ((end == null) || (end >= stack.length)) end = stack.length - 1
        if (start < 0) start = 0
        while (start < end) {
            let mid = Math.floor((start + end) / 2)
            let test = stack[mid]
            if (test.from == where) {
                let ini=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
                    }
                }
                return resp
            } else if (where < test.from) end = mid - 1
            else start = mid + 1
        }
        return []
    }
}