Analysis: Haywire by Jonathan Paulson and Brian Dean
For N = 12, this problem was (as intended!) a bit more challenging to solve in time. There are a few approaches one can use to accomplish this. First, we can recursively generate all 12! orderings, but we can be clever as we go and "prune" our search any time we realize that our current partial solution will never end up better than the best complete solution found so far.
In the code below, we recursively build up all 12! orderings. The variables cows_so_far and cost_so_far tell us the number of cows and the cost of the links between these cows in the partial solution built so far. The pending_links variable tells us the number of links that have started in our partial solution but not yet terminated (so these links will go to cows we have not yet added); pending_link_cost tells us the sum of lengths so far of all these links. Observe that pending_link_cost is a lower bound on the cost of completing our solution, so if we ever reach a point where this cost plus the cost of the completed links in our partial solution is larger than the cost of the best solution found so far, we can immediately prune the search, back up, and try other possibilities. As a result, we end up streamlining our search and generating far fewer than all possible 12! orderings.
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int N;
int nbr[13][3];
int best = 9999999, cow_pos[13];
void solve(int cows_so_far, int cost_so_far, int pending_links, int
pending_link_cost)
{
if (cows_so_far==N) {
best = min(best, cost_so_far);
return;
}
/* Prune search if no hope of beating the best solution found so far... */
if (cost_so_far + pending_link_cost >= best) return;
cows_so_far++;
for (int i=1; i<=N; i++)
if (cow_pos[i] == 0) {
cow_pos[i] = cows_so_far;
int added_cost = 0, new_pending_links = 3;
for (int j=0; j<3; j++)
if (cow_pos[nbr[i][j]] != 0) {
added_cost += cow_pos[i] - cow_pos[nbr[i][j]];
new_pending_links -= 2;
}
solve(cows_so_far,
cost_so_far + added_cost,
pending_links + new_pending_links,
pending_link_cost + (pending_links + new_pending_links) - added_cost);
cow_pos[i] = 0;
}
}
int main(void)
{
ifstream fin("haywire.in");
ofstream fout("haywire.out");
fin >> N;
for (int i=1; i<=N; i++) {
for (int j=0; j<3; j++) {
fin >> nbr[i][j];
}
}
solve(0, 0, 0, 0);
fout << best << "\n";
return 0;
}
We now turn to slightly more algorithmically advanced techniques, which we
discuss here for completeness. It is often possible to turn O(n!) algorithms
into O(2^n) algorithms with
dynamic programming (Traveling Salesman is a classic example); let's try it
here. Define f(set) to be the minimum cost arrangement given that the cows in
set are in the first |set| positions. This, unfortunately, isn't well-defined;
it depends on what order the cows are in, which is exactly what we were trying
to forget in the first place!
The problem with the previous approach was that we needed to remember where we placed cows so we could pay for their friendships later. We can salvage the idea by paying for friendships incrementally, not all at once. Imagine placing 1 cow at a time, and building 1 segment of wire in that position for each friendship that will need to cross it. We can compute the number of friendships that need to cross a particular cow given only the set of cows that have been placed (it is just the number of friendships between cows in the set and cows outside of the set). And if we place all the cows in this way, paying for one segment of wire at a time, when we get to the end we will have paid for all the wire we needed for this arrangement.
This solution runs in O(2^n * n). There are 2^n subsets, and n choices for which cow to add next.
There is also a divide-and-conquer approach: pick the first 6 cows and the last six cows, brute force both halves in 6! time, and then compute the # of edges that cross between the halves. Charge the wire to get to the half-way mark as part of the cost of each half, so that the two problems are independent. This approach is (12 choose 6)*6! = 665,000 operations, well within the time limit.
One little programming trick: the Java solution below keeps track of set (the set of cows used so far) and out (the number of friendships that are between a cow in set and a cow not in set), even though out is not part of the DP state. This is OK, because out is uniquely determined by set. Maintaining information that is not part of your DP state but is determined by it often leads to more convenient code.
Here is a Java implementation of the DP idea:
public class haywire {
static boolean bit_set(int set, int bit) {
return ((set>>bit)&1)==1;
}
static int n;
static List<List<Integer>> E = new ArrayList<List<Integer>>();
static boolean[] S;
static int[] DP;
static int f(int set, int out) {
if(set == (1<<n)-1) return 0;
if(S[set]) return DP[set];
S[set] = true;
int ans = 1000*1000;
for(int x=0; x<n; x++) {
if(bit_set(set, x)) continue;
int new_out = out;
for(Integer y:E.get(x)) {
if(bit_set(set, y)) new_out--;
else new_out++;
}
ans = Math.min(ans, new_out + f(set|(1<<x), new_out));
}
return DP[set] = ans;
}
public static int i(String s) { return Integer.parseInt(s); }
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("haywire.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("haywire.out")));
n = i(in.readLine());
S = new boolean[1<<n];
DP = new int[1<<n];
for(int i=0; i<n; i++) E.add(new ArrayList<Integer>());
for(int i=0; i<n; i++) {
String[] arr = in.readLine().split("\\s+");
E.get(i).add(i(arr[0])-1);
E.get(i).add(i(arr[1])-1);
E.get(i).add(i(arr[2])-1);
}
out.println(f(0, 0));
out.flush();
}
}
Here is a C++ implementation of the DP idea:
#define NMAX 12
#define infinite 1000000000
int dp[1 << NMAX];
int main() {
#ifndef HOME
freopen("haywire.in","r",stdin);
freopen("haywire.out","w",stdout);
#endif
int n;
scanf("%d", &n);
int a1[12], a2[12], a3[12];
for (int i = 0; i < n; i++) {
scanf("%d %d %d", &a1[i], &a2[i], &a3[i]);
a1[i]--;
a2[i]--;
a3[i]--;
}
dp[0] = 0;
for (int subset = 1; subset < (1 << n); subset++) {
int totalOut = 0;
for (int i = 0; i < n; i++) {
if (subset & (1 << i)) {
totalOut += 3 - (((subset >> a1[i]) & 1) +
((subset >> a2[i]) & 1) +
((subset >> a3[i]) & 1));
}
}
dp[subset] = infinite;
for (int i = 0; i < n; i++) {
if (subset & (1 << i)) {
int cost = totalOut - 3 + 2 * (((subset >> a1[i]) & 1) +
((subset >> a2[i]) & 1) +
((subset >> a3[i]) & 1));
dp[subset] = min(dp[subset], dp[subset & ~(1 << i)] + cost);
}
}
}
printf("%d\n", dp[(1 << n) - 1]);
}
Here is a C++ implementation of the divide-and-conquer idea:
int N;
int E[12][3];
int A[12];
int B[12];
int C[1 << 12];
int D[1 << 12];
bool cn[12][12];
int main() {
freopen("haywire.in", "r", stdin);
freopen("haywire.out", "w", stdout);
cin >> N;
for(int i = 0; i < N; i++) {
for(int j = 0; j < 3; j++) {
cin >> E[i][j]; E[i][j]--;
cn[i][E[i][j]] = true;
}
}
memset(C, 0, sizeof(C));
memset(D, 0x1F, sizeof(D));
for(int i = 0; i < 1 << N; i++) {
int M = 0;
for(int j = 0; j < N; j++) {
if(i & 1 << j) {
A[M++] = j;
for(int k = 0; k < 3; k++) {
if(~i & 1 << E[j][k]) {
C[i]++;
}
}
}
}
if(M > N / 2) continue;
int& r = D[i];
memset(B, 0, sizeof(B));
do {
for(int j = 0; j < M; j++) {
B[A[j]] = j;
}
int s = 0;
for(int j = 0; j < M; j++) {
for(int k = 0; k < 3; k++) {
s += max(0, j - B[E[A[j]][k]]);
}
}
r = min(r, s);
} while(next_permutation(A, A + M));
}
int res = 0x7FFFFFFF;
for(int i = 0; i < 1 << N; i++) {
res = min(res, D[i] + D[~i & (1 << N) - 1] + C[i]);
}
cout << res << endl;
return 0;
}