- Thoughts.
- Estimating computational quantities
- The number of vertices is 8, so it’s OK to search all of them in the factorial.
- I usually have graphs with adjacency lists, but this time it’s an adjacency matrix.
- For each permutation, just check “Does it have an edge?
- If there’s no edges along the way, it’s impossible to search ahead, so I’d prefer to use depth-first search to prune the branches.
- Official Explanation OK
- I’m assuming the solution above, but bit DP says it’s O(N^2 2^N).
- You have the number of cases where you start at point X for all subsets, follow them all, and end at point Y.
- I’m assuming the solution above, but bit DP says it’s O(N^2 2^N).
This page is auto-translated from /nishio/ABC054C using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.