Solving SPOJ ACPC10G, maraghuram.github.io

SPOJ ACPC10G The Problem

There are N knights and N points on an infinite chessboard. Each knight should occupy exactly one of the points. The knight's moves are the same chess moves (L shaped). What is the minimum number of moves required by all the knights?
Note, the problem states that more than one knight can occupy a single cell while trying to reach its final destination.
1 ≤ N ≤ 15
Click here for complete problem description

Let $ X = { X_1, X_2, ... X_N} $ denote an arrangement of knights and $ Y = { Y_1, Y_2, ... Y_N} $ a corresponding set of points such that the knight X_i occupies the point Y_i.
The cost of such an arrangment is $ Cost(X,Y) = \sum_{i=1}^N KnightCost(X_i,\;Y_i) $ .
This problem asks to find the minimum such value of $ Cost(X,Y) $.
Finally, the additional note is hinting that each knight can be positioned independent of other knights.

I stumbled across this problem while looking at the wonderful collection of dynamic programming problems by Zobayer. So, I know this problem has a DP solution, but let's say I didn't know that. Then, how to find out if a problem has a DP solution and solve it?
It is useful to check for these characteristics - Not necessary for every DP problem though

The first solution one can think of (brute-force method) results in an exponential/intractable problem space

Unusual limits/Low problem constraints, but would still TLE for brute-force solutions

The problem repeats itself in a smaller problem space (sub-problems)

An optimal solution to the problem can be derived from a finite number of sub-problems

Let's try to apply them one by one

The simplest solution would be to generate every permutation of the knight-point matching and calculate the total cost for each permutation. The minimum of these is the answer.
Complexity of such a solution: O(N!),
Naive brute-force methods result in an intractable problem space
Complexity of brute-force solution translates to atleast 15! (1307674368000) operations for the given problem. This would definitely exceed the 0.14s time limit on the SPOJ Cube cluster.
If you are not sure on time limits and estimating operations based on algorithmic complexity, you should look at them before starting on any problem. There are a number of resources on the internet for different platforms (Codechef, Topcoder, Codeforces, Spoj). This book on Competitive Programming by Steven Halim has an entire section on Algorithm Analysis.
Even though the limits are unusually low (N ≤ 15), the brute force solution is not enough.
The hardest question: Does this problem repeat itself with a smaller problem space? Thinking in terms of permutations doesn't help in reducing the problem since the permutations are independent of each other
Again, Let $ X = \{ X_1, X_2, ... X_N\} $ denote the knights and $ Y = \{Y_1, Y_2, .. Y_N\} $ denote the points. $ MinCost(X, Y) $ denotes the minimum sum of cost for matching these knights and points.
Let's say we match a knight $ X_i $ and position $ Y_j $ that the knight needs to occupy. This would mean a cost of $ KnightCost(X_i, Y_j) $ and then again we are left with a set of $ N - 1 $ knights and points that need to be matched with minimum sum of costs!

In other words, when $ X_i $ is matched with $ Y_j $, $$ MinCost(X, Y) = KnightCost(X_i, Y_j) + MinCost(X-\{X_i\}, Y-\{Y_j\}) $$
So, the problem definitely has a repeating structure.
We still don't have a solution- to find out the minimum cost for N knights and points. So let's try to formalize the base cases and recursive structure for the problem. $$ MinCost[N][Y] = minimum \{ ( KnightCost(N,j) + MinCost[N-1][Y-\{j\}] ) \; \forall j \; \in Y \} $$ Base cases simply match $ X_1 $ with every point ($ size(Y) = 1 $) $$ MinCost[1][\{Y_1\}] = KnightCost(1, 1) \\ MinCost[1][\{Y_2\}] = KnightCost(1, 2) \\ .. $$ Therefore, the optimal solution can be dervived from at most $ N $ sub-problems.

Complexity Analysis:

Using bitmasks to represent the subsets of $ Y $, Memory limits: $ O(N \cdot 2^N) $
Time Limit:

The dp state space consists of $ O(N \cdot 2^N) $ states
Cost to compute the optimal solution for every state $ O(N) $
Therefore, total time complexity: $ O(N^2 \cdot 2^N) $

Final Notes and Implementation:

No. of operations based on the worst case time complexity: ($ 15 \cdot 15 \cdot {2}^{15} $) ~ 7 million operations
An important assumption here is that knight distance between two points X, Y can be computed quickly. This is also a well known topic and I won't be solving it here.
$ O(N^2 \cdot 2^N) $ is actually quite close to the Time Limit. A couple of tips while implementing,
- Think of how you can retrieve knight-point distances in O(1) for DP
- $ O(N^2 \cdot 2^N \cdot T) $ where T is number of test cases is definitely TLE!

C++ Implementation:

If you have any questions or comments, feel free to leave them below.

Solving SPOJ ACPC10G

SPOJ ACPC10G The Problem

Complexity Analysis:

Final Notes and Implementation:

Happy Practicing!