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
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.
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