21 Mar 2015

The problem editorial is here: http://apps.topcoder.com/wiki/display/tc/SRM+651#FoxConnection3

I couldn't solve this problem on my own. With the low limit of foxes, I didn't realise we could brute-force for the optimal solution.

Since I cannot find a link to the problem statement, I post the problem statement here:

The infinite plane is divided into a grid of unit square cells. Two cells are considered adjacent if they share a side.

There are some foxes on the plane. Each fox is currently standing on a different cell. This must also be preserved in the future - there cannot be two foxes in the same cell at the same time.

Whenever a fox takes a step, it moves to a cell that is adjacent to its current cell. A set of cells is considered connected if a fox could walk from any cell in the set to any other cell in the set without leaving the set.

All foxes want to get together. More precisely, they want to move in such a way that at the end the set of cells occupied by the foxes is connected.

Return the smallest total number of steps the foxes need to make in order to reach such a configuration.

And there are, at most, 6 foxes. Because the number of foxes is low, we can find all possible forms of n-connected cells. For examples, the number of possible 6-connected cells is only 216. The number of assignments (permutations) of 6 things is 6! = 720.

720 x 216 iterations is not big at all. Therefore, we can look at every pattern-and-assignment and select the one with minimum steps.

Let's assume we have one pattern of 6-connected cells and one permutation. Let's define the assumption with the fox i is currently at (Xi, Yi) and will move to (Si, Wi).

There is still one crucial information missing: where does the 6-connected-cells pattern locate?

We need to define the offset (Ox, Oy) to locate the position of the pattern. Now that we have every information, we can move the foxes to their destination. The cost is calculated with the below formula:

cost = sum of for all i, |Ox - Xi + Si| + |Oy - Yi + Wi|

Please note that Xi, Si, Yi, and Wi are constants here because we are calculating for one pattern and one assignment. We want to find (Ox, Oy) that results in the minimal steps.

I went into the wrong direction here. I thought that the optimal (Ox, Oy) would be at one of the foxes. It turns out that it is false. Ox and Oy might be on the same fox or might not be. (4,0), (0,4), (-4,0), (0,-4), (2,2) are the example where Ox and Oy are not on the same fox; Ox and Oy are 0 and 0, respectively.

For the optimal solution, Ox is at one of the foxes, and Oy is at one of the foxes. The proof with induction is simple and is left as an exercise for myself.

Generating all the possible patterns of 6 connected cells can be done with backtracking. We can do it with breadth-first search as well, but it might be costly because there would be many arrays allocated; with backtracking, we can re-use the same array.

One other thing is that we need to find a good strategy for not visiting redundant patterns. For example, (0,0), (0,1), (1,1), (1,0) are equivalent to (0,0), (0,-1), (-1,-1), (-1,0). My strategy is (1) to find minX and minY to normally all coordinates to be greater than or equal to (0,0), (2) sort the coordinates, (3) generate a string of sorted coordinates, and (4) store the string in a hash.

Generating all possible assignments can be done with backtracking as well. We avoid selecting already-used number using bitfields to store the numbers. We can achieve it because there are only 6 numbers.

Next, we iterate through every pattern and assignment, compute steps, and get minimal steps.

Here's my full code:

```
import java.util.*;
public class FoxConnection3 {
Coordinate[] move = new Coordinate[] {
new Coordinate(1, 0),
new Coordinate(-1, 0),
new Coordinate(0, 1),
new Coordinate(0, -1)
};
ArrayList<Coordinate[]> patterns = new ArrayList<Coordinate[]>();
ArrayList<int[]> assignments = new ArrayList<int[]>();
Set<String> visitedSignature = new HashSet<String>();
Set<String> storedPattern = new HashSet<String>();
private Coordinate[] sanitized;
public static void main(String[] args) {
new FoxConnection3().process();
}
public void process() {
int[] x = new int[]{-96277832, 507856257, -86306299, -806700273, -775932643, -273209838};
int[] y = new int[]{-955536464, -599634138, 399850429, -165706338, -537800480, 738983556};
System.out.println(minimalSteps(x, y));
}
public long minimalSteps(int[] x, int[] y) {
int N = x.length;
fillPatterns(N);
fillAssignments(N);
long minCost = Long.MAX_VALUE;
for (int p = patterns.size() - 1; p >= 0; p--) {
Coordinate[] pattern = patterns.get(p);
for (int a = assignments.size() - 1; a >= 0; a--) {
int[] assignment = assignments.get(a);
long minCostX = Long.MAX_VALUE;
long minCostY = Long.MAX_VALUE;
for (int i = 0; i < N; i++) {
long dx = pattern[assignment[i]].x - x[i];
long dy = pattern[assignment[i]].y - y[i];
long costX = 0;
long costY = 0;
for (int j = 0; j < N; j++) {
costX += Math.abs((long) pattern[assignment[j]].x - (long) x[j] - dx);
costY += Math.abs((long) pattern[assignment[j]].y - (long) y[j] - dy);
}
if (minCostX > costX) minCostX = costX;
if (minCostY > costY) minCostY = costY;
}
if (minCost > (minCostX + minCostY)) minCost = minCostX + minCostY;
}
}
return minCost;
}
public void fillAssignments(int n) {
int[] temp = new int[n];
fillAssignments(0, temp, 0);
System.out.println("assignments = " + assignments.size());
}
private void fillAssignments(int index, int[] temp, int used) {
if (index == temp.length) {
int[] result = new int[temp.length];
for (int i=0;i<temp.length;i++) {
result[i] = temp[i];
}
assignments.add(result);
return;
}
for (int i=0;i<temp.length;i++) {
if ((used & (1 << i)) > 0) { continue; }
temp[index] = i;
fillAssignments(index + 1, temp, used | (1 << i));
}
}
public void fillPatterns(int n) {
sanitized = new Coordinate[n];
Coordinate[] current = new Coordinate[n];
for (int i=0;i<n;i++) {
sanitized[i] = new Coordinate(0, 0);
current[i] = new Coordinate(0, 0);
}
generate(0, 0, current);
System.out.println("patterns = " + patterns.size());
}
public void generate(int currIndex, int index, Coordinate[] current) {
String pattern = getSignature(currIndex, current);
String signature = pattern + "-" + index;
if (visitedSignature.contains(signature)) {
return;
} else {
visitedSignature.add(signature);
}
if (currIndex == (current.length - 1)) {
if (!storedPattern.contains(pattern)) {
Coordinate[] copy = new Coordinate[current.length];
for (int i = 0; i < current.length; i++) {
copy[i] = current[i].getCopy();
}
patterns.add(copy);
storedPattern.add(pattern);
}
return;
}
for (int i=0;i<move.length;i++) {
current[currIndex + 1].x = current[index].x + move[i].x;
current[currIndex + 1].y = current[index].y + move[i].y;
boolean visited = false;
for (int j=0;j<=currIndex;j++) {
if (current[currIndex + 1].equals(current[j]) && (currIndex + 1) != j) {
visited = true;
break;
}
}
if (visited) { continue; }
for (int j=0;j<=(currIndex+1);j++) {
generate(currIndex + 1, j, current);
}
}
}
private String getSignature(int index, Coordinate[] current) {
int minX = current[0].x;
int minY = current[0].y;
for (int i=1;i<=index;i++) {
if (minX > current[i].x) minX = current[i].x;
if (minY > current[i].y) minY = current[i].y;
}
for (int i=0;i<=index;i++) {
sanitized[i].x = current[i].x - minX;
sanitized[i].y = current[i].y - minY;
}
Arrays.sort(sanitized, 0, index + 1, comparator);
StringBuilder sb = new StringBuilder();
for (int i=0;i<=index;i++) {
sb.append('(');
sb.append(sanitized[i].x);
sb.append(',');
sb.append(sanitized[i].y);
sb.append(')');
}
return sb.toString();
}
Comparator<Coordinate> comparator = new Comparator<Coordinate>() {
public int compare(Coordinate a, Coordinate b) {
int compareX = a.x - b.x;
int compareY = a.y - b.y;
if (compareX != 0) {
return compareX;
} else {
return compareY;
}
}
};
class Coordinate {
public int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public Coordinate getCopy() {
return new Coordinate(x, y);
}
public String toString() {
return "(" + x + "," + y + ")";
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Coordinate that = (Coordinate) o;
if (x != that.x) return false;
if (y != that.y) return false;
return true;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
}
```