Indoorienteering

Introduction

This problem whether a graph contains a hamiltonian cycle of a given length.

Solutions

Brute Force

Idea

Hamiltonian Cycle is NP complete ....must do brute force. Iterate over all possible permutations of points and check the length.

Further, it's clear it's brute-force-ish because n=14.

Runtime

• n! = 87178291200

Fixed Starting Point

Idea

It's a cycle, so therefore we'll reach every point. If we fix a start point, we eliminate a dimension.

Runtime

• (n-1)! = 6227020800

Divide and Conquer

Idea

Split the points up into two equal halves. Compute the lengths of each side to see if any of the possibilities add up. Fix the midpoint so the calculation of each side has a fixed start and end point.

Runtime

• (n-1 choose n/2) * n/2! * n/2!
• (n-1)!/(n/2!)^2 * (n/2!)^2
• (n-1)! :(

Divide and Conquer with Hashmap

Idea

When you compute the first side, store all the lengths into the hashset. When you compute the second half, simply check whether the hashmap contains total length minus length second half length. Here we see why it's important to fix the midpoint. Without a fixed midpoint, we can't calculate the two halves independent of each other, as the distance of side 1 would depend on the first point on side 2 (and vice versa).

Runtime

• (n-1 choose n/2) * (n/2! + n/2!)
• n-1!/(n/2!)^2 * 2 * n/2!
• 2 * (n-1)! / (n/2!) = 17,297,280

Code

Solution - Java

import java.util.*;
public class i {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new i().go();
	}
	private void go() {
		int n=in.nextInt();
		long l=in.nextLong();
		long[][] d=new long[n][n];
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=in.nextLong();
		if(n==2){
			System.out.printf("%s\n", d[0][1]+d[1][0]==l?"possible":"impossible");
			System.exit(0);
		}
		for(int i=1;i<n;i++){//it's a cycle...assume it starts at 0 with midpoint i
			for(int j=0;j<1<<(n-2);j++)if(Integer.bitCount(j)==(n-2)/2&&j<(j^((1<<(n-2))-1))){
				int[] inn=new int[(n-2)/2],out=new int[n-2-(n-2)/2];
				int inni=0,outi=0;
				for(int k=1;k<n;k++)if(k!=i){//skip the breakpoint
					if(((j>>(k-(k>i?2:1)))&1)==1)inn[inni++]=k;
					else out[outi++]=k;
				}
				HashSet<Long> l1=solve(inn,d,0,i);
				HashSet<Long> l2=solve(out,d,i,0);
				for(long ls:l1)if(l2.contains(l-ls)){
					System.out.println("possible");
					System.exit(0);
				}
			}
		}
		System.out.println("impossible");
	}
	private HashSet<Long> solve(int[] inn, long[][] d,int f,int l) {
		HashSet<Long> r=new HashSet<Long>();
		if(inn.length==0){
			r.add(d[f][l]);
			return r;
		}
		do{
			long ans=0;
			ans+=d[f][inn[0]];
			ans+=d[inn[inn.length-1]][l];
			for(int i=0;i<inn.length-1;i++)ans+=d[inn[i]][inn[i+1]];
			r.add(ans);
		} while(nextPermutation(inn));
		return r;
	}
	public boolean nextPermutation(int[] in){
		for(int i=in.length-2;i>=0;i--)if(in[i]<in[i+1]){
			for(int j=in.length-1;j>i;j--)if(in[j]>in[i]){
				int t=in[i];
				in[i]=in[j];
				in[j]=t;
				break;
			}
			for(int j=i+1;j<in.length-(j-i);j++){
				int t=in[j];
				in[j]=in[in.length-(j-i)];
				in[in.length-(j-i)]=t;
			}
			return true;
		}
		return false;
	}
}