MMA CTF 2015 - Task Pattern Lock
We are asked to calculate the number of ways to make a valid pattern on Android lock screen. This problem is equivalent to counting different simple Hamiltonian paths on a graph. Since the number of nodes are small (but big enough so that we can't use a backtracking algorithm for the second flag with 16 nodes, because it would run in ), I used DP with bitmask to calculate the first flag with complexity about
(Of course we can Google that one, but we still need to code for the second flag, so...)
And, for the second flag, we just need to change the optimization function a bit:
The first flag is 389112, the second flag is 45.6790.
