Dijkstra algorithm is for finding the shortest path in the graph - that is the one with the minimum sum of edge weights. Another constraint is that all weights must be non-negative. This is coming from how the algorithm works (by gradually extending the current path in a BFS manner using edge weight as priority/order).
The wikipedia article is quite detailed: https://en.wikipedia.org/wiki/Dijkstra's_algorithm
Here we need the maximum cost path of the graph which is different from the minimum. If you simply multiply all weights by (-1), then minimum becomes maximum, but then your weights will become negative and the algo will fail. You can use Floyd-Warshall or Bellman-Ford algorithms (see https://en.wikipedia.org/wiki/FloydāWarshall_algorithm, https://en.wikipedia.org/wiki/BellmanāFord_algorithm for explanation and pseudocode) to find the minimum cost path of the graph with negative weights, but these algorithms are computationally more complex than Dijkstra. For me, they timeouted above 5000 rooms.
In the end, a simple DFS with some memoization was the working AND fast-enough solution for me, and not any of these generic graph algorithms.
[disclaimer] this could be a spoiler
Iāve made this :
// start function with R = first room
function(R)
1. if R has no neighbors, go to (5.)
2. for each neighbors of R,
2.0. if neighbour is marked as visited, T = neighbour.money + neighbour.total, go to (2.2.)
2.1. T = function(neighbour)
2.2. add T to L
3. R.total = highest value of L
4. mark R as visited
5. return R.money + R.total
I just wonder if that algo has a name, it look like something between IDA* and the Backpropagation of a MCTS, anyone ?
Hi there
I use a BFS kind of solution.
The longest test takes 12 ms.
The test are all good, but when I submit, I get between two and six tests ok, and with every submit, there are other tests that work, even without changing anything on the code.
I have no idea how this i possible
I implemented with Dijkstra but failed at test case 04 (Found: 379, expected: 358).
Would you please help to check from which part, my solution will return the incorrect value.
import java.util.*
import java.io.*
import java.math.*
fun main(args : Array<String>) {
val input = Scanner(System.`in`)
val N = input.nextInt()
if (input.hasNextLine()) {
input.nextLine()
}
val edges: Array<IntArray> = Array(N + 1) { IntArray(N + 1) }
for (i in 0 until N) {
val room = input.nextLine()
val data = room.split(" ")
val roomNumber = data[0].toInt()
val money = data[1].toInt()
(2..data.size - 1)
.map {
if (data[it] == "E") {
N
} else {
data[it].toInt()
}
}
.forEach {
edges[roomNumber][it] = money
}
}
println(dijkstra(0, edges, N))
}
fun dijkstra(start: Int, edges: Array<IntArray>, end: Int): Int {
val V = IntArray(end + 1)
val Q = (0..end).toMutableList()
while (Q.isNotEmpty()) {
val u = extractMax(Q, V)
edges[u].forEachIndexed { index, value ->
if (value != 0 && V[index] < V[u] + value) {
V[index] = V[u] + value
}
}
}
return V[end]
}
fun extractMax(Q: MutableList<Int>, V: IntArray): Int {
var maxNode = Q[0]
var maxValue = V[0]
Q.forEach {
if (V[it] > maxValue) {
maxValue = V[it]
maxNode = it
}
}
Q.remove(maxNode)
return maxNode
}
I think it is better for you to check your code yourself, given this is a hard puzzle and you are relatively skilled. I can give you the breakdown of the answer so it may be easier for you to check:
I fixed my implementation by changing the way to calculate the cost but seems we cannot use Dijkstra algorithm in this scenario as Dijkstra only return the max value at the traversal time but may be not the maximum one after finish traversal
So far, Iāve coded a sort of modified Djikstraās algorithm. I know itās not working in all situations, especially if there are cycling paths, but thatās not my main problem for now. When I execute my code against the third test (15 rooms), my code find a path that earns 127. But the response should be 88.
Iāve checked manually the solution found by my algorithm and Iāva come up with the same result.
This probably means that I missed or misunderstood one of the puzzleās rules, but I canāt find which one.
The puzzle data :
Room Id
Room Mny
Link 1
Link 2
0
17
1
2
1
15
0
4
2
15
4
5
3
20
1
7
4
12
2
8
5
11
8
9
6
18
3
11
7
19
4
12
8
12
5
13
9
11
13
14
10
13
6
-1
11
14
7
6
12
17
8
7
13
19
9
8
14
15
-1
9
-1
0
10
14
(Iāve made a beautiful graph from this data to paste here, only to discover new users canāt upload images. Sorry).
The solution found by my algo is :
0 ā 1 ā 4 ā 2 ā 5 ā 8 ā 13 ā 9 ā 14 ā -1
17 + 15 + 12 + 15 + 11 + 12 + 19 + 11 + 15 = 127
The problem may lay in my understanding of the rule āBlunder can never go backā. I thought first that it means blunder cannot travel to an already visited room (which my solution complies with). In a second time I thought that maybe it means that he cannot travel to a room that have an Id inferior to the current room Id, but in this case the max money I earn is 69.
So anybody here can help me find what I am doing wrong please ?
Iām so ashamed !
Iām using an external IDE and I must have changed the test case for some reason I canāt remember.
With the correct set of data, it eventually works.
Thanks for pointing me the good direction and for the usefull tip for accessing test cases data !
Lately Iāve been trying to use the generic pathfinder implementations in scipy and this felt like a good case for it. Indeed, once the input is prepared I could get the answer in one line, but it timed out on the 9870 rooms case. I spent some time trying to optimize it. In the end the simplest recursive DFS with memoization solved it.
I used a dijkstraās algorithm with some modifications to maximize the paths instead of find minimum like the original one.
But I cannot pass the largest dataset.
I get a timeout in 5050 and 9870 rooms. Every other test is passed
The main takeaway from this puzzle should be that a modified Dijkstraās algorithm for solving the longest path can be applied only because of the constraints of this problem definition (specific floor layout). Do not be mislead that you can apply Dijkstra for longest path categorically.
