Link to Problem (Contest, Practice)

I did a randomized tree construction algorithm and bombed the complement graph, with heavy pruning and bit counting, magic compression, and solved most of the exact subtasks for 90.414 points.

However, I was not able to solve for the “smallish” subtask with n \leq 40. I tried doing some meet-in-the-middle brute force but I was not able to formulate a good approach for it. We can also discuss other solutions, but I’m specifically curious about the “smallish” subtask since it would have been able to dramatically boost my algorithm. Any ideas from the codechef community?