SRM 652, D1, 500-Pointer (MaliciousPath)

James S. Plank

Thu Nov 1 21:27:45 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2015
Competitors who opened the problem: 439
Competitors who submitted a solution: 59
Number of correct solutions: 31
Accuracy (percentage correct vs those who opened): 7.1%
Accuracy (percentage correct vs those who submitted): 52.5%
Average Correct Time: 40 minutes, 45 seconds.

If you are programming this up and need some help debugging, I have put output files which print each A and B vector for each example, into: Ex-0.txt, Ex-1.txt, Ex-2.txt, Ex-3.txt, Ex-4.txt and Ex-5.txt.

This is a wonderful Dijkstra-esque problem (and no, I didn't get it on my own).

Let's define two quantities of nodes:

A_i(n): This is Alice's shortest path from node n to the last node, given that Bob has i tokens. Obviously, A_K(0) is the answer to the problem.
B_i(n): This is Alice's shortest path from node n to the last node, given that Bob has i tokens left, and he plays one of them right now on node n.

As it turns out, you can calculate A_i from B_i using a Dijkstra-like calculation, and you can calculate B_i from A_i-1 really easily.

Taking a look at A_i and B_i in Example 0

Here's the graph of example 0, with the A_i values filled in. You can calculate these using Dijkstra's algorithm, but using node 2 as the starting node, and reversing all of the edges. You'll note, I simply delete any edges coming out of node 2, because they won't be useful to this problem --- once Alice reaches node 2, she's done.

Next, I'm going to calculate B₁ for each of the nodes. This is the shortest path that Alice can take if Bob gets to choose the edge out of each of these nodes. Since nodes 0 and 2 have at most one edge coming out of them, for them, B₁ equals A₀. However, with Node 1, Bob has a choice. If he chooses the edge to node 2, then the path length is one. However, if he chooses the edge to node 0, then the path length is (2 + A₀(0)) = 6. Obviously, Bob will choose that edge. Here are the B₁ values:

Time to work on A₁. To restate, A₁(n) is Alice's shortest path from n the last node, given that Bob has one token, meaning Bob can choose her edge exactly once:

With node 2, Alice is done, so A₁(2) equals zero.
With node 1, we consider two cases: If the choice is up to Alice, she'd go to node 2 directly. However, if the choice is up to Bob, he'll make her go to node 0. Since Bob has a token, he'll play it here, so A₁(1) = B₁(1) equals 6.
With node 0, Alice only has one choice, to go to node 1, with Bob still having his token. So in this case, A₁(0) = 3 + A₁(1) equals 9.

Those values are below:

Once we have A₁, we can calculate B₂ from them. Recall that B₂(n) is Alice's shortest path from node n given that Bob has two tokens, and he uses one of them on node n. The way that you determine B₂(n) is to look at every edge going from n. Suppose that edge is e = (n,m). Then Bob wants to choose the edge such that (Weight(e) + A₁(m)) is maximized.

For B₂(0), there is only one edge, so B₂(0) equals (3 + A₁(1)) equals 9.
For B₂(1), there are two edges:
1. The edge to node 0: (2 + A₁(0)) equals 11.
2. The edge to node 2: (1 + A₁(2)) equals 1.
Clearly, Bob will choose the edge to node 0: B₂(1) equals 11.
For B₂(2), it has to equal zero.

Updated picture:

And let's do one more -- calculating A₂. We do this from node 2 back to node 0:

As always, A₂(2) equals zero.
With node 1, once again, if Alice were to choose, she'd to go node 2 directly. However, since Bob has a token, he'll play it, and her best path is equal to B₂(1). Therefore, A₂(1) equals 11.
With node 0, as before, Alice only has one choice, to go to node 1, with Bob still having his tokens. So in this case, A₂(0) = 3 + A₂(1) equals 14.

Updated picture:

You can spot the pattern here -- A_i(0) equals 4+5i. This is why the answer to example zero is 5004.

I know I've walked through this very slowly, but I want you to understand how you calculate B_i from A_i-1, and how you calculate A_i from a combination of B_i and other nodes' A_i.

The algorithm for A_i

I assume at this point, that you can write the code to calculate B_i, so let's focus now on A_i. The algorithm for choosing A_i(n) is as follows:

If Alice gets to choose, then she is going to consider all outgoing edges e = (n,m). She will choose the edge that minimizes her path -- in other words the edge that minimizes (Weight(e) + A_i(m)). You'll note that for Alice to determine this value, either A_i(m) has to be known, or Alice has to know somehow that (Weight(e) + A_i(m)) is bigger than her shortest path (this is where Dijkstra's algorithm is going to come in).
If the path that results when Alice chooses has a length that is greater than B_i(n), then Bob can keep his token. A_i(n) will equal this path length. This is what happened above with node 0 when we determined A₁(0) and A₂(0). However, if Alice's path is shorter than B_i(n), then Bob is going to uses his token. This is what happened above with node 1, when we determined A₁(1) and A₂(1).

Armed with this information, we can calculate all of the A_i(n) using Dijkstra's algorithm, starting with the last node and reversing the edges. We'll start by setting A_i(n) to ∞ for all n, except the last node. We'll set that A_i to zero and put it on the multimap.

The heart of Dijkstra's algorithm looks as follows:

- Pull node n with distance d off of the multimap.
- For every edge from n to m, do the following:
   - If we've visited m already, skip it.
   - Take a look at the path length to m through n.  Call this value newd.
   - If newd < m's current distance, then:
       - Update m's current distance to newd.
       - Put m on the multimap, keyed by newd.
       - (Decide what to do if m was already on the multimap.  I leave it there).

We need to modify the heart of this algorithm to do the calculation above. Here's the psuedocode:

- Pull node n with distance d off of the multimap.
- For every edge from n to m, do the following:
   - If we've visited m already, skip it.
   - Take a look at the path length to m through n.  Call this value newd.
   - If newd < B_i(m), then set newd to B_i(m).
   - If newd < m's current distance, then:
       - Update m's current distance to newd.
       - Put m on the multimap, keyed by newd.
       - (Decide what to do if m was already on the multimap.  I leave it there).

The line in blue is the new line. It says, "If Alice finds a path that is less than B_i(n), then Bob is going to use his token, because he doesn't want to allow Alice to use that path."

I hope this helps you understand the calculation of A_i(n). I can tell you that I had a hard time with it, which is why this writeup is so long. Have fun!

In case you care, here was my class definition

class MaliciousPath {
  public:
    long long minPath(int N, 
                      int K, 
                      vector <int> from, 
                      vector <int> to, 
                      vector <int> cost);
    vector < vector <int> > Adj;            // Adjacency lists
    vector < vector <int> > Radj;           // Reverse adjacency lists
    vector < vector <long long> > Weights;  // Weights
    vector < vector <long long> > RWeights; // Reverse weights
    vector <int> Visited;                   // Visited field for Dijkstra.
    vector <long long> A;                   // A - I replace this for each different i.
    vector <long long> B;                   // B - I replace this for each different i.
    void FirstDijkstra();                   // The Dijkstra to determine A_0
    void NextDijkstra();                    // The Dijkstra to determine the other A_i
    long long bll;                          // Infinity (0x100000000000LL).
};

I didn't realize until after I wrote this writeup that you don't need FirstDijkstra(). You can simply set B₀(n) -1, and NextDijkstra() will work for A₀(n).