Minimum Penalty Path Discussions | Algorithms | HackerRank
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. Minimum Penalty Path
  5. Discussions

Minimum Penalty Path

Sort by

recency

|

57 Discussions

|

  • C_jain
     + 0 comments

    Golang solution just in case someone is looking. NOTE: Dijkstra will not work as explained [here]https://www.hackerrank.com/challenges/beautiful-path/forum/comments/121506). We need to go with brute force as input size is small, so a simple dfs/bfs needed to check all possible distances of a vertex from starting vertex(in this case 'A').

    package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
    "math"
)

/*
 * Complete the 'beautifulPath' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. 2D_INTEGER_ARRAY edges
 *  2. INTEGER A
 *  3. INTEGER B
 */

func beautifulPath(n int32, edges [][]int32, A int32, B int32) int32 {
    const INF = int32(1024)
    
    adjList := edgeListToAdjList(n, edges)

    var queue [][]int32
    queue = append(queue, []int32{A, 0})
    
    dist := initDist(n)
    dist[A][0] = true
    
    result := INF
    
    for len(queue) > 0 {
        front := queue[0]
        u := front[0]
        d := front[1]
        
        queue = queue[1:]
        
        for _, edge := range adjList[u] {
            v := edge[0]
            w := edge[1]
            
            newDistForV := d | w
            
            if !dist[v][newDistForV] {
                dist[v][newDistForV] = true
                
                queue = append(queue, []int32{v, newDistForV})
                
                if v == B {
                    result = int32(math.Min(float64(result), float64(newDistForV)))
                }
            }
        }
    }
    
    if result == INF {
        return -1
    }
    
    return result
}

func initDist(V int32) map[int32]map[int32]bool {
    dist := make(map[int32]map[int32]bool)
    
    for i := int32(0); i <= V; i++ {
        dist[i] = make(map[int32]bool)
    }
    
    return dist
}

func edgeListToAdjList(V int32, edgeList [][]int32) [][][]int32 {
    adjList := make([][][]int32, V+1)
    
    for _, edge := range edgeList {
        u := edge[0]
        v := edge[1]
        w := edge[2]
        
        adjList[u] = append(adjList[u], []int32{v, w})
        adjList[v] = append(adjList[v], []int32{u, w})
    }
    
    return adjList
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    firstMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    nTemp, err := strconv.ParseInt(firstMultipleInput[0], 10, 64)
    checkError(err)
    n := int32(nTemp)

    mTemp, err := strconv.ParseInt(firstMultipleInput[1], 10, 64)
    checkError(err)
    m := int32(mTemp)

    var edges [][]int32
    for i := 0; i < int(m); i++ {
        edgesRowTemp := strings.Split(strings.TrimRight(readLine(reader)," \t\r\n"), " ")

        var edgesRow []int32
        for _, edgesRowItem := range edgesRowTemp {
            edgesItemTemp, err := strconv.ParseInt(edgesRowItem, 10, 64)
            checkError(err)
            edgesItem := int32(edgesItemTemp)
            edgesRow = append(edgesRow, edgesItem)
        }

        if len(edgesRow) != 3 {
            panic("Bad input")
        }

        edges = append(edges, edgesRow)
    }

    secondMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    ATemp, err := strconv.ParseInt(secondMultipleInput[0], 10, 64)
    checkError(err)
    A := int32(ATemp)

    BTemp, err := strconv.ParseInt(secondMultipleInput[1], 10, 64)
    checkError(err)
    B := int32(BTemp)

    result := beautifulPath(n, edges, A, B)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, csharp HackerRank Minimum Penalty Path Solution

  • seonandla
     + 0 comments

    Hi There! i want to use it for my Gaming Website .

  • mineman1012221
     + 0 comments

    Here is the solution of Minimum Penalty Path Click Here

  • junkmann
     + 1 comment

    It can be solved pretty easily by using brute force since the maximum edge cost is pretty small (1023).

    The key observation to make is that the answer lies between 1 and 1023, if there is a path from A to B, otherwise -1. So you can just test if it's possible to get from A to B with a cost of 1, 2, 3, ... up to 1023. So all that is left is to create a graph where the OR of all its edges results to the cost you are testing for.

    public static int beautifulPath(List<List<int>> edges, int A, int B)
{
	--A;
	--B;

	var edgesGroupedByCost = new List<(int U, int V)>[1024];

	for (var c = 0; c < 1024; ++c) {
		edgesGroupedByCost[c] = new();
	}

	foreach (var edge in edges) {
		var u = edge[0] - 1;
		var v = edge[1] - 1;
		var c = edge[2];

		edgesGroupedByCost[c].Add((u, v));
	}

	var ds = new DS(1000);

	for (var r = 1; r < 1024; ++r) {
		ds.Clear();

		for (var c = 1; c < 1024; ++c) {
			if ((r | c) == r) {
				foreach (var (u, v) in edgesGroupedByCost[c]) {
					ds.Union(u, v);
				}
			}
		}

		if (ds.Find(A) == ds.Find(B)) {
			return r;
		}
	}

	return -1;
}

    I used a disjoinct set data structure to see if A and B are connected in the resulting graph but I'm pretty sure just doing a DFS from A to see if you can reach B works too.