TopCoder: MaliciousPath (SRM 652)

1 Apr 2015

For this problem, I was lost a few times, and the obstacles made me stuck for a very long time.

The first obstacle was that I didn't formulate the problem properly. After deciding to formulate it, the problem became clear to me. This is a turn-by-turn game. Therefore, we need to formulate each turn (not the whole game). Let's formulate each turn:

  1. Assume that Alice is on the node x and x can go to the nodes in Y and that Bob has k tokens. We use this: f(k, x)
  2. Alice always chooses the optimal path. Therefore, Alice chooses y in Y that w(x,y) + f(k,y) is the smallest value
  3. Bob always maximise Alice's path. Therefore, Bob chooses y in Y that w(x,y) + f(k-1,y) is the biggest value
  4. If Bob has a token, he always win the decision. Therefore, the formula is f(k, x) = max { max y {w(x,y) + f(k-1,y) }, min y { w(x,y) + f(k,y) } }. Please note that, if the shortest path is already the highest one, then Bob doesn't need to spend a token.
  5. If Bob doesn't have a token (k=0), Alice always win the decision. Therefore, the formula is f(0,x) = min y { w(x,y) + f(k,y) }.

It becomes clear that the problem looks like a dynamic programming problem. However, there can be a loop since f(k,x) depends on f(k-1,y) and f(k,y), and x might point to y and vice versa.

If we look closely, a loop is not actually real because it doesn't make sense to travel through x -> y -> x unless Bob uses a token. In fact, x shouldn't go to y at all if y is not a part of the shortest path. This means if we process node is the correct order, we can ignore the cycle altogether. Dijkstra's algorithm does exactly that in order to find the shortest path.

With the above explanation, we can start with computing f(k,x) in the increasing order of k. My second obstacle was here. I didn't realise I needed to pre-compute B(k,y) = max y {w(x,y) + f(k-1,y) } before performing Dijkstra's algorithm. When I didn't pre-compute B(k,y), it became extremely complicated because I needed to maintain the max {...} and maintain the min {..}. I couldn't find an algorithm that achieved this task.

But if we pre-compute B(k,y), f(k,x) becomes max { B(k,y), min y { w(x,y) + f(k,y) } }, and Dijkstra's algorithm does the minimum part for me. Please note that B(k,y) is a constant

Here's the code:

import java.util.*; public class MaliciousPath { public long minPath(int N, int K, int[] from, int[] to, int[] cost) { ArrayList[] sources = new ArrayList[N]; for (int i=0;i<N;i++) sources[i] = new ArrayList(); for (int i=0;i<from.length;i++) { int src = from[i]; int dest = to[i]; int weight = cost[i]; sources[dest].add(new Edge(src, weight)); } long infinity = Long.MAX_VALUE / 2; long[] costFromBobUsingToken = new long[N]; long[] distance = new long[N]; for (int i=0;i<N;i++) costFromBobUsingToken[i] = 0; NodeComparator comparator = new NodeComparator(); for (int k=0;k<=K;k++) { PriorityQueue<Node> queue = new PriorityQueue<Node>(N, comparator); queue.add(new Node(N-1, 0)); for (int i=0;i<N;i++) distance[i] = infinity; distance[N-1] = 0; while (!queue.isEmpty()) { Node node = queue.poll(); // this entry is not the optimal one, we must discard it. // Otherwise, there would be infinite loop if (node.cost != distance[node.nodeIndex]) continue; for (Object edgeObj: sources[node.nodeIndex]) { Edge edge = (Edge) edgeObj; long aliveMoveToSrcCost = edge.weight + node.cost; long selectedCost = Math.max(costFromBobUsingToken[edge.srcIndex], aliveMoveToSrcCost); if (selectedCost < distance[edge.srcIndex]) { distance[edge.srcIndex] = selectedCost; queue.add(new Node(edge.srcIndex, selectedCost)); } } } for (int i=0;i<N;i++) { for (Object edgeObj: sources[i]) { Edge edge = (Edge) edgeObj; costFromBobUsingToken[edge.srcIndex] = Math.max(costFromBobUsingToken[edge.srcIndex], distance[i] + edge.weight); } } } if (distance[0] >= infinity) return -1; else return distance[0]; } public class Edge { public int srcIndex; public long weight; public Edge(int srcIndex, long weight) { this.srcIndex = srcIndex; this.weight = weight; } } public class Node { public int nodeIndex; public long cost; public Node(int nodeIndex, long cost) { this.nodeIndex = nodeIndex; this.cost = cost; } } class NodeComparator implements Comparator<Node> { @Override public int compare(Node a, Node b) { if (a.cost < b.cost) { return -1; } else if (a.cost > b.cost) { return 1; } else { return 0; } } @Override public boolean equals(Object obj) { return false; } } }