ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1972. Game Testing

Hints & ideas
Posted by decay 1 May 2019 18:36
A problem asks to find longest path in Hyper cube graph that visits each vertex at most once.

If two numbers have odd amount of bits in common then there is always a Hamiltonian path (length 2^n). Parity of common bits is checked using xor.

If parity is even then one can build a path of length 2^n - 1. This path can be built by
successively building Hamiltonian paths on lower dimension cube. That is, build a path of length 2^(n - 1) and recurse to find path of length 2^(n - 1) - 1.

So, the solution is built around knowing how to construct Hamiltonian path.

There is, in fact, a very simple approach. My algorithm works in O(2^n) and doesn't use extra memory.