Camelot

We are given an $$r \times c$$ chessboard $$(1 \leq R \leq 30, \ 1 \leq C \leq 26)$$ where some cells have knights and one cell has a king.The knights and king can move freely, and there can be more than one piece in any cell at any time (the cells are very "large"). The goal is to select a cell for all of the pieces to meet in, in such a way that the sum of the number of moves taken by all pieces is minimal. At any point, if a king and a knight occupy the same cell, the king may join with the knight, and the two pieces become one knight piece.
  1. Euler tour?
  2. Shortest paths
  3. Floyd-Warshall algorithm
  4. Pick a knight to pick-up the king
  5. Greedy (always meet on a king, or a knight?)
Algorithm 1.1
Use floyd-warshall to compute all shortest paths by knight and by king.
For each (meeting-point s, pick-up-point p, knight to pick up the king k):
	cost(s,p,k) = dist(k,p,by_knight) + dist(king,p,by_king) + dist(p,s,by_knight)
	For each knight h != k:
		cost(s,p,k) += dist(h,s)
return min(cost(s,p,k)) over all (s,p,k)
Basically the main idea is to use Floyd-Warshall to compute all the distances. We then pick a knight to go pick up the king, and also a cell where they should meet. Given a meeting cell, a pick-up cell, and a knight, we can use the previously computed distances to calculate the total sum of distances / moves. Take the minimum over all such choices, and this must be our answer. This approach is correct. However, it is far too slow. The Floyd-Warshall algorithm alone runs in $$O(N^3)$$ time where $$N = R \times C$$ is the number of cells, which can be around 800. So, this approach got TLE.
Since the number of nodes is too high, an $$O(N^3)$$ algorithm is too slow. Therefore, I need an algorithm that is based on some greedy observation or on classic "shortest path" algorithms, if I hope to solve this problem.
The conditions are complicated and not independent. How does the problem vary when we drop some combination of the conditions?
How do we solve this problem if we were not given any king at all?
If we have no king, we simply have to find the s which minimizes the sum of distances to all knights. Doing Floyd-Warshall is still too slow here, so we can't use it at all. However, we can use Dijkstra's algorithm, once from each possible "meeting-point", to compute the distances, and then take the sum. There is probably no better way to solve this modified problem anyway. With Dijkstra's algorithm, we can solve this in $$O(NlogN)$$ time per "meeting-point". So we get $$O(N^2logN)$$ in total, which is better than $$O(N^3)$$.
What if we only have a king (no knights)?
If we just have a king, we should always just place the meeting point on the king (obviously). If we (for some reason) still had to go through all meeting points, the answer is just $$\max(dx,dy)$$ where $$dx$$ and $$dy$$ are the absolute differences of $$x$$ and $$y$$ coordinate from the king to the meeting point; we would then try all meeting points (this solution would likely be $$O(N)$$).
What if we have a king, but we need not "pick-up" the king?
Then these problems are independent. We simply proceed with dijkstra's, computing the distances, and also computing the king distance. We then sum over these and take the minimum meeting point.
In attempting to generalize to the "pick-up-the-king" version, the above simplifications reminded me of something which I've heard called "2D-Dijkstra". In essence, we use a modified version of Dijkstra's algorithm, maintaining more than one value (i.e.: a pair, triple, tuple, or list of values) at each node; the values will be modified similarly to with Dijkstra's algorithm, but may not directly correspond to a "shortest" path (or may correspond to a shortest path on some auxiliary graph).
Given a fixed meeting-point $$s$$, can we do some kind of modified Dijkstra's algorithm (or possibly a 2D-Dijkstra) to solve the main problem? (It seems like this is the right approach based on the simplified problems; we have to try each source anyway, it seems.)
Assume that we have a fixed meeting cell $$s$$, and a king starting at some fixed cell $$k$$. Take any cell $$(r,c)$$; Take any path from $$(r,c)$$ to $$s$$. We define the detour distance of this path to be the total number of steps that a knight would take on this path, plus the minimum number of steps that it would take for the king $$k$$ to move to some cell on this path.
That is, the detour distance of this path is the total number of moves needed if a knight at $$(r,c)$$ were to go pick up the king somewhere on this path, and the king were to move to that cell, and then they would travel together (as one knight) to $$s$$.
With a fixed meeting cell $$s$$ and a king $$k$$, we define the detour distance of the cell $$(r,c)$$ to be the minimum detour distance over all paths from $$(r,c)$$ to $$s$$. The detour distance of cell $$(r,c)$$ will be denoted $$f(r,c)$$.
The goal is that, hopefully, these "detour distances", defined as above, can be computed via Dijkstra's algorithm in some way.
Two cells $$(r,c)$$ and $$(r',c')$$ are said to be neighbors if a knight on cell $$(r,c)$$ can move to cell $$(r',c')$$ in one step.
How do detour distances of neighbors relate? In particular, can we generate formulas and inequalities that relate detour distances of neighbors similarly to regular distances?
After fiddling around with some formulas, we get the following lemma.
\[f(r,c) \leq \min_{\text{neighbors} (r',c')}{f(r', c') + 1}\]
Take any optimal solution (i.e.: a path which generates a shortest detour distance) for $$(r,c)$$. There are two cases: either the king comes to this cell, or it does not. If the king must come to that cell, then the "detour distance" of any knight starting on that cell is the sum of the number of moves it takes for the king to get to that cell and for a knight to go from that cell to the meeting-point $$s$$. If the king will not go to that cell, then any knight starting on $$(r,c)$$ which is to pick up the king must travel at least one unit away. Hence, it must travel through some neighboring cell $$(r',c')$$ (which takes 1 step). After that, we can take the shortest path to pick up the king and go to the end from there (which takes $$f(r',c')$$ steps by definition). And this can be extended to any pair of neighbors. $$(r,c)$$ can always take a path through $$(r',c')$$. So, $$f(r,c) \leq (r',c') + 1$$. Furthermore, there must be some neighbor for which this applies (or else the first case applies, and the king must travel to the cell $$(r,c)$$). This proves the statement.
We can apply a modified version of Dijkstra's algorithm to solve this problem.
See analyses of the Algorithm below. Also, see my tutorial on shortest paths. Generally speaking, we have a graph where the nodes are the cells, and there are edges of length 1 between neighbors, and the weight of the "empty" path is some number dependent on the vertex it is on.
Let $$d(r,c)$$ be the distance (by knight) from cell $$(r,c)$$ to point $$s$$. Let $$f(r,c)$$ be the detour distance from cell $$(r,c)$$ to point $$s$$. MEETING-POINT(R, C, king_r, king_c, knights):
ans = infinity
For each possible meeting-point s:
	Compute d(r,c) over all cells (r,c) by Dijkstra from s.
	For each cell (r,c):
		f(r,c) = d(r,c) + (distance from king to (r,c) by king-steps)
	while(f(r,c) > f(r',c') + 1) for some neighbors (r,c) and (r',c'):
		Choose the (r',c') with the minimum f(r',c') value
		Set f(r,c) = f(r',c') + 1
The above algorithm is equivalent to running Dijkstra's algorithm on an auxiliary graph which would return the correct detour distances.
For each cell $$(r,c)$$ we define two auxiliary nodes: $$(r,c,no)$$ and $$(r,c,yes)$$ to represent a knight being on cell $$(r,c)$$ without the king, or with the king (respectively). We construct a graph on these auxiliary nodes so that an edge exists between $$(r,c,no)$$ and $$(r',c',no)$$ of length 1 if $$(r,c)$$ and $$(r',c')$$ are neighbors by knight. Similarly, an edge exists between $$(r,c,yes)$$ and $$(r',c',yes)$$ of length 1 for neighbors $$(r,c)$$ and $$(r',c')$$ by knight. Now, an edge exists between $$(r,c,no)$$ and $$(r,c,yes)$$ of length equal to the minimum steps it would take to get from the king to the cell $$(r,c)$$ by king-steps. Informally, we can model this problem by knights either "taking a step" or "calling the king". The king does not move until some knight specifically calls it to the knight's cell. Then, the king will travel directly to that cell, and the knight will now "have" the king; and the knight can then move on, taking steps again. Once the king has been "called" to the knight at cell $$(r,c)$$, the knight moves from state $$(r,c,no)$$ to state $$(r,c,yes)$$. So, the total number of "steps" needed to transition from $$(r,c,no)$$ to $$(r,c,yes)$$ was exactly the number of steps it took the king to get to cell $$(r,c)$$. Then, the detour distance $$f(r,c)$$ to a fixed cell $$s = (sr,sc)$$ can actually be seen as the shortest path distance from $$(r,c,no)$$ to $$(sr,sc,yes)$$. That is, we must eventually end up at cell $$s$$, and we must eventually have the king. This corresponds to eventually ending up in cell $$(sr,sc,yes)$$. And the minimum weight path over all these is the solution. (Note: This also gives us an alternative algorithm for solving this problem.) To show the reduction from our algorithm above to the shortest path algorithm described in this proof, we notice that, for any cell $$(r,c)$$, the distance from $$(r,c,yes)$$ to $$(sr,sc,yes)$$ is just the length of the shortest direct path (i.e.: minimum number of steps a knight must take to get there, $$d(r,c)$$). Once a knight has the king, the knight can simply move directly to the sink cell $$s$$. So, for a node $$(r,c,no)$$, the length of the path is no more than the length of the path $$(r,c,yes)$$ plus the cost of achieving/calling the king. This is equal to $$d(r,c) + \text{(distance from king to (r,c) by king-steps)}$$. And this is exactly what we initialize $$f(r,c)$$ to for each node $$(r,c)$$. Then, after some iterations, we update $$f(r,c)$$ based on the edges, which is equivalent to updating the distances of nodes $$(r,c,no)$$ based on neighbors $$(r',c',no)$$. Hence, our above algorithm is equivalent to running Dijkstra's algorithm on this auxiliary graph; but our algorithm automatically fills in the distances for the $$(r,c,yes)$$ nodes to be $$d(r,c)$$ (which they would be by the end of Dijkstra's algorithm anyway) and skips directly to the point in the algorithm where the $$(r,c,no)$$ nodes need to filled in. So, in the end $$f(r,c)$$ will be set exactly equal to the proper detour distance according to a reduction to this auxiliary graph.
Upon termination of the algorithm above, $$f(r,c)$$ will be equal to the detour distance of cell $$(r,c)$$.
We could also solve this problem by doing Dijkstra's algorithm directly on the auxiliary graph. This would be an alternative approach
The above algorithm can be made to run in $$O(N \log N)$$ time using the priority queue version of Dijkstra's algorithm.
In the end, this problem was reducible to solving shortest paths on multiple sources. Whenever one has multiple-source shortest-paths, the immediate idea is to use Floyd-Warshall's algorithm for this, due to its simplicity to code. However, the Floyd-Warshall algorithm runs in $$O(N^3)$$ (where N is the number of edges) whereas (at least for sparse graphs with small edges, in this case), simply calling Dijkstra's algorithm once for each source is $$O(N^2 \log N)$$ or something similar, which is much faster. In fact, in this problem, with $$N=800$$, Floyd-Warshall was utterly impossible. Once having decided that we want to use some variant of Dijkstra's algorithm once for each "source" (where I am using a "source" to mean "final meeting place"; it might be better to call it a "sink", but hopefully the reader understands), it is not easy to figure out "how" to use Dijkstra's algorithm here. The key realization is that, for a knight on cell $$(r,c)$$ either the king will go there directly, or the cell will have to make at least one step before meeting the king. This "at least one step" property is the key property that allows this problem to be solvable by Dijkstra's algorithm. Specifically, that means that the "detour distance" of a cell $$(r,c)$$ is no more than the detour distance of any of its knightly-neighbors, plus 1. This yields an inequality that smells a lot like the shortest-path inequalities: $$f(r,c) \leq f(r',c') + 1$$ over all neighbors $$(r',c')$$ (where neighbors are those which can be reached in one knight-step). After working this out, one comes to either a reduction to an auxiliary graph (where the states are the cells, along with an additional bit for whether the knight has the king or not), or a modified Dijkstra's algorithm that computes these $$f(r,c)$$ directly. This problem was neat because it was a nice demonstration of modified shortest paths, especially non-trivial reductions. It also showed that, anytime we can get a system of inequalities of the form: $$f(x) \leq f(x') + w(x,x')$$, then we can likely solve the problem via shortest paths in some form or another.
  1. $$f(r,c) \leq \min_{\text{neighbors} (r',c')}{f(r', c') + 1}$$ (the detour distance of a cell is no more than 1 plus the detour distance of its neighbor). This was the crucial observation. It took me all of my mental capabilities to get to this observation (probably because I was too busy thinking about optimizing the Floyd-Warshall brute-force approach). But the way I realized this was by applying some problem solving processes (namely, "drop and/or vary the conditions", or "simplify the problem") and realizing that, even under a simplified version of this problem, Dijkstra's algorithm would be required in some capacity.
  2. This problem is reducible to Dijkstra's algorithm on an auxiliary graph. This became immediately intuitive once we realized the inequalities. It was much harder to prove this though. In the end I simply wrote the code for a "modified dijkstra's algorithm" that appeared correct; and it took me several attempts at this analysis before I could formally prove its correctness. In the end, my formal proof of correctness relied on reducing it to another algorithm (which was more literally an application of Dijkstra's algorithm); I would have liked to use a more direct proof. But nonetheless, sometimes it is better to code first and prove later, for problems that are "intuitive but hard to prove".
  1. Recognizing more quickly that an $$O(N^3)$$ algorithm is too slow would have saved me a lot of time on this problem. Being able to recognize the necessity for a greedy or classic shortest-path algorithm would have been an asset.
  2. The conditions / constraints (meet up at a place, pick up king, shortest path, etc.) were far to interrelated and dependent. A good problem-solving technique is to vary the constraints, drop different combinations of the constraints, and solve simpler forms of the problem, in order to determine what underlying structures there are inherent to the problem. For me, this meant asking the questions:
    1. What happens if there is no king?
    2. What happens if there is only a king and no knights? (With variations on this)
    3. What about if there are kings and knights, but they can't "combine"?
    These lead to some insights about the structure of this problem. For example, without a king, we still have to perform some kind of dijkstra's algorithm from each source, since Floyd-Warshall is too slow anyway.
  3. I remembered the buzz-words: "2D-Dijkstra" and "modified Dijkstra". Once I decided that I wanted to use shortest-paths, I focused my attention on these kinds of algorithms (variants of Dijkstra's algorithm), which eventually became the final solution.
  • Shortest Paths / Dijkstra's Algorithm / Modified Dijkstra
  • Shortest Paths / All-Pairs Shortest Paths / Sparse Graphs
  • Checkerboard / Chess Board / Knights and Kings
  • Intuition / Intuitive but Hard to Prove problems
  • Graph Theory / Shortest Paths
  • Steiner Trees / Minimum Spanning Trees?
  • I need to ask good questions (i.e.: the "problem-solving questions"). By asking "How does this problem change when I vary / drop some conditions", I was able to better understand the structure of the problem and then solve it.
  • Anytime I have a set of objects, and a function over that set of objects that preserves some inequalities of the form: $$f(x) \leq f(y) + w(y,x)$$, then we can apply shortest path algorithms. We can apply shortest path algorithms in more general (but very similary) settings, depending on our definitions of $$``+", ``\leq",$$ and $$w(y,x)$$. As such, I decided to write a tutorial / post analyzing the general shortest-path problem. See the tutorial here.
  • Try FIXING one of the parameters (in this case, the source/sink cell).