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