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. Graph Theory
  4. Jeanie's Route
  5. Discussions

Jeanie's Route

  • shanefostersmith
     + 0 comments

    Java solution. First, remove outer, non-letter cities (will never be visited). Then, from the (new) outer letter cities, go inward until you reach an intersection city (3 or more edges) and calculate the minimum and maximum subtree value. You can consider a 'minimum' subtree is where you start or end a path at that subtree. A maximum subtree will double value of all "lines" in the subtree. Eventually, you will reach an inner city in which all subtrees are calculated. From there you can calculate an intersection's cities minimum path will add two minimum subtrees with the rest as maximum subtrees. Once you've reached the most inner intersection city, you can calculate it's minimum path and move back outerwards to calcuate the rest of the intersections minimum paths (with optimizations). One of the intersections will have the minimum path, and that's what you will return. Minimum is O(# cities), maximum is O(# cities + # edges).

    static int jeanisRoute(int[] k, int[][] roads) {
        int biggestCity = roads.length + 1;
        // Trivial Cases
        if (biggestCity == 2) {
            return roads[0][2];
        }
        if (biggestCity == 3 && k.length == 3 ) {
            int sum = 0;
            for (int i = 0; i < 2; i++) {
                sum += roads[i][2];
            }
            return sum;
        }
        Set<Integer> letterCities = new HashSet<>();
        for (int i = 0; i < k.length; i++) {
            letterCities.add(k[i]);
        }
        Map<Integer,List<Integer>> adjList = new HashMap<>();
        Map<Edge,Integer> weights = new HashMap<>();
        // Create adjacency list
        for (int i = 1; i <= biggestCity; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int i = 0; i < roads.length; i++) {
            int[] currRoad = roads[i];
            int vertex1 = currRoad[0];
            int vertex2 = currRoad[1];
            adjList.get(vertex1).add(vertex2);
            adjList.get(vertex2).add(vertex1);
            Edge newEdge = new Edge(vertex1,vertex2);
            weights.put(newEdge,currRoad[2]);
        }
        if (biggestCity == 3) {
            int sum = 0;
            for (int i = 0; i < k.length; i++) {
                List<Integer> connected = adjList.get(k[i]);
                if (connected.size() == 1) {
                    int connectedCity = connected.get(0);
                    Edge newEdge = new Edge(k[i],connectedCity);
                    if (letterCities.contains(connectedCity)) {
                        return weights.get(newEdge);
                    } else {
                        sum += weights.get(newEdge);
                    }
                }
            }
            return sum;
        }
        int citiesLeft = biggestCity;
        Set<Integer> outerCities = new HashSet<>();
        
        // Remove non-letter cities that will never be visited (outer of graph)
        // Create set of "outer cities"
        for (int i = 1; i <= biggestCity; i++) {
            List<Integer> connectedCities = adjList.get(i);
            if (connectedCities.size() != 1) {
                continue;
            }
            if (letterCities.contains(i)) {
                outerCities.add(i);
            } else { // Current City will never be visited
                int currCity = i;
                while (true) {
                    int adjCity = adjList.get(currCity).get(0);
                    adjList.get(currCity).remove(0);
                    List<Integer> connectedToAdj = adjList.get(adjCity);
                    for (int j = 0; j < connectedToAdj.size(); j++) {
                        if (connectedToAdj.get(j) == currCity) {
                            connectedToAdj.remove(j);
                            break;
                        }
                    }
                    citiesLeft--;
                    if (adjCity > i || connectedToAdj.size() != 1) {
                        break;
                    }
                    if (letterCities.contains(adjCity)) {
                        outerCities.add(adjCity);
                        break;
                    }
                    currCity = adjCity;
                }
            }
        }
        
        // For every 'intersection' can choose two subtrees to be minimum and 
        // rest be maximum. Choose intersection that is minimal. 
        Map<Integer, int[][]> interToMinMaxSubtrees = new HashMap<>();
        Map<Integer, Integer> interMaxTotal = new HashMap<>();
        Map<Integer, int[]> interDiffMaxMin = new HashMap<>();
        Map<Integer, Set<Integer>> interToVisitedEdges = new HashMap<>();
        Map<Integer, Integer> interNumTreesCalculated = new HashMap<>();
        int noIntersection = 0;
        Set<Integer> nextCities = new HashSet<>();
        // Start with Outer Cities to Intersection Cities
        for (int outer : outerCities) {
            System.out.println("Curr Outer: " + outer);
            citiesLeft--;
            int prevCity = outer;
            int currCity = adjList.get(outer).get(0);
            int currLen = weights.get(new Edge(prevCity,currCity));
            while (true) {
                List<Integer> connectedToCurr = adjList.get(currCity);
                int numConnected = connectedToCurr.size();
                if (numConnected > 2) { // Found intersection city
                    // Find edge index it currently intersected with
                    int edgeIntersect = 0;
                    for (int i = 0; i < numConnected; i++) {
                        int connectedCity = connectedToCurr.get(i);
                        if (connectedCity == prevCity) {
                            edgeIntersect = i;
                            break;
                        }
                    }
                    // Update maps
                    interToVisitedEdges.computeIfAbsent(currCity, 
                    key -> new HashSet<>()).add(edgeIntersect);
                    
                    int[][] minMax = interToMinMaxSubtrees.computeIfAbsent(currCity, key ->
                    new int[numConnected][2]);
                    minMax[edgeIntersect][0] = currLen;
                    minMax[edgeIntersect][1] = 2*currLen; 
                    
                    interMaxTotal.put(currCity, 
                    interMaxTotal.getOrDefault(currCity, 0) + minMax[edgeIntersect][1]);
                    
                    int edgesSeen = interToVisitedEdges.get(currCity).size();
                    interNumTreesCalculated.put(currCity, edgesSeen);
                    
                    interDiffMaxMin.computeIfAbsent(currCity, 
                    key -> new int[2]);
                    if (edgesSeen == numConnected - 1) {
                        nextCities.add(currCity);
                    }
                    int[] currLargest = interDiffMaxMin.get(currCity);
                    if (currLen < currLargest[0]) {
                        break;
                    }
                    if (currLen > currLargest[1]) {
                        currLargest[0] = currLargest[1];
                        currLargest[1] = currLen;
                    } else {
                        currLargest[0] = currLen;
                    }
                    break;
                }
                // This city is part of a 'line'
                if (numConnected == 2) {
                    citiesLeft--;
                    int nextCity = connectedToCurr.get(0) == prevCity ? 
                    connectedToCurr.get(1) : connectedToCurr.get(0);
                    currLen += weights.get(new Edge(currCity, nextCity));
                    prevCity = currCity;
                    currCity = nextCity;
                    continue;
                }
                // Went from outer city to outer city, no intersections
                noIntersection = currLen;
                break;
            }
            if (noIntersection > 0) {
                return noIntersection;
            }
        }
        // Only one intersection
        if (citiesLeft == 1) {
            int intersection = (int) interMaxTotal.keySet().toArray()[0];
            int[] largestSubTrees = interDiffMaxMin.get(intersection);
            int result = interMaxTotal.get(intersection) - 
            largestSubTrees[0] - largestSubTrees[1];
            return result;
        }
        Queue<Integer> toCalculate = new LinkedList<>();
        Map<Integer,int[][]> interToInterCityAndLen = new HashMap<>();
        
        int totalMax = 0;
        boolean[] calculated = new boolean[biggestCity];
        while (true) {
            Set<Integer> newCities = new HashSet<>();
            for (int inter : nextCities) {
                List<Integer> connectedToInter = adjList.get(inter);
                Set<Integer> edgesVisited = interToVisitedEdges.get(inter);
                if (edgesVisited.size() == connectedToInter.size()) {
                    continue;
                }
                int prevCity = inter;
                int lineStartIdx = 0;
                int currCity = 0;
                for (int i = 0; i < connectedToInter.size(); i++) {
                    if (!edgesVisited.contains(i)) {
                        currCity = connectedToInter.get(i);
                        lineStartIdx = i;
                        break;
                    }
                }
                
                // If intersection to intersection already calculated
                if (interToInterCityAndLen.get(inter) != null && interToInterCityAndLen.get(inter)[lineStartIdx][0] != 0) {
                    continue;
                }
                int currLen = weights.get(new Edge(prevCity,currCity));
                while (true) {
                    List<Integer> connectedToCurr = adjList.get(currCity);
                    int numConnected = connectedToCurr.size();
                    
                    // This city is part of a 'line'
                    if (numConnected == 2) {
                        int nextCity = connectedToCurr.get(0) == prevCity ? 
                        connectedToCurr.get(1) : connectedToCurr.get(0);
                        currLen += weights.get(new Edge(currCity,nextCity));
                        prevCity = currCity;
                        currCity = nextCity;
                        continue;
                    }
                    // Found intersection
                    
                    // Find edge index that was intersected
                    int edgeIntersect = 0;
                    for (int i = 0; i < numConnected; i++) {
                        int connectedCity = connectedToCurr.get(i);
                        if (connectedCity == prevCity) {
                            edgeIntersect = i;
                            break;
                        }
                    }
                    interToVisitedEdges.computeIfAbsent(currCity, 
                    key -> new HashSet<>()).add(edgeIntersect);
                    
                    // Update intersection connections
                    int[] connectCurrToInter = {currCity,edgeIntersect,currLen};
                    int[] connectInterToCurr = {inter,lineStartIdx,currLen};
                    interToInterCityAndLen.computeIfAbsent(currCity, 
                    key -> new int[numConnected][3])[edgeIntersect] = connectInterToCurr;
                    interToInterCityAndLen.computeIfAbsent(inter, 
                    key -> new int[numConnected][3])[lineStartIdx] = connectCurrToInter;
                    
                    // Find min and max of current subtree
                    int previousMax = interMaxTotal.get(inter);
                    int prevLargestSubTree = interDiffMaxMin.get(inter)[1];
                    int previousMin = interMaxTotal.get(inter) - prevLargestSubTree;
                    int currentMax =  2*currLen + previousMax;
                    int currentMin = previousMin + currLen;
                    int diffMaxMin = currentMax - currentMin;
                    
                    // Update maps
                    interMaxTotal.put(currCity, 
                    interMaxTotal.getOrDefault(currCity, 0) + currentMax);
                    
                    int minMax[][] = interToMinMaxSubtrees.computeIfAbsent(currCity ,
                    key -> new int[numConnected][2]);
                    minMax[edgeIntersect][0] = currentMin;
                    minMax[edgeIntersect][1] = currentMax;
                    
                    interNumTreesCalculated.put(currCity, 
                    interNumTreesCalculated.getOrDefault(currCity, 0) + 1);
                    interDiffMaxMin.computeIfAbsent(currCity, 
                    key -> new int[2]);
                    int[] currLargest = interDiffMaxMin.get(currCity);
                    if (diffMaxMin > currLargest[1]) {
                        currLargest[0] = currLargest[1];
                        currLargest[1] = diffMaxMin;
                    } else if (diffMaxMin > currLargest[0]) {
                        currLargest[0] = diffMaxMin;
                    }
                    int edgesSeen = interToVisitedEdges.get(currCity).size();
                    if (edgesSeen == numConnected - 1) {
                        newCities.add(currCity);
                    } else if (edgesSeen == numConnected) {
                        newCities.remove(currCity);
                        if (interNumTreesCalculated.get(currCity) == numConnected) {
                            totalMax = interMaxTotal.get(currCity);
                            toCalculate.add(currCity);
                        }
                    }
                    break;
                } // while loop inner end
            } // for loop end
            if (newCities.isEmpty()) {
                break;
            } 
            nextCities = newCities;
        }
        
        int minSeen = Integer.MAX_VALUE;
        // only visit intersections where all subtrees have been calculated
        while (!toCalculate.isEmpty()) {
            int currInter = toCalculate.poll();
            if (calculated[currInter - 1]) {
                continue;
            }
            // Calculate minimum path for this city
            calculated[currInter - 1] = true;
            int[] currLargest = interDiffMaxMin.get(currInter);
            int result = totalMax - currLargest[1] - currLargest[0];
            if (result < minSeen) {
                minSeen = result;
            }
            // Calculate subtree for neighboring city
            int[][] connectedToCurr = interToInterCityAndLen.get(currInter);
            for (int i = 0; i < connectedToCurr.length; i++) {
                int connectedCity = connectedToCurr[i][0];
                if (connectedCity == 0 || calculated[connectedCity - 1]) {
                    continue;
                }
                int numSubTreesTotal = adjList.get(connectedCity).size();
                int numSubTreesCalculated = interNumTreesCalculated.get(connectedCity);
                int treesLeft= numSubTreesTotal - numSubTreesCalculated;
                if (treesLeft == 0) {
                    continue;
                }
                // Calculate subtree from connected to current
                int connectedLen = connectedToCurr[i][2];
                int[][] currMaxMin = interToMinMaxSubtrees.get(currInter);
                int maxRemoved = currMaxMin[i][1];
                int minRemoved = currMaxMin[i][0];
                int diffRemoved = maxRemoved - minRemoved;
                int connectedMaxSubTree = totalMax - maxRemoved + 2*connectedLen;
                int connectedMinSubTree;
                if (diffRemoved < currLargest[1]) {
                    connectedMinSubTree = connectedMaxSubTree - currLargest[1];
                }
                else  {
                    connectedMinSubTree= connectedMaxSubTree - currLargest[0];
                }
                connectedMinSubTree += connectedLen;
                int connectedDiff = connectedMaxSubTree - connectedMinSubTree;
                int[] largestDiffs = interDiffMaxMin.get(connectedCity);
                if (connectedDiff > largestDiffs[1]) {
                    largestDiffs[0] = largestDiffs[1];
                    largestDiffs[1] = connectedDiff;
                } else if (connectedDiff > largestDiffs[0]) {
                    largestDiffs[0] = connectedDiff;
                }
                // This city will never be the minimum
                if (largestDiffs[1] + largestDiffs[0] <= currLargest[1] + currLargest[0]) {
                    continue;
                }
                // Update maps for connected
                interNumTreesCalculated.put(connectedCity,++numSubTreesCalculated);
                if (--treesLeft == 0) {
                    toCalculate.add(connectedCity);
                } 
                int subTreeIdx = connectedToCurr[i][1];
                int[][] connectedMinMax = interToMinMaxSubtrees.get(connectedCity);
                connectedMinMax[subTreeIdx][0] = connectedMinSubTree;
                connectedMinMax[subTreeIdx][1] = connectedMaxSubTree;
            }
        }
        return minSeen;
    }