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?
My solution
2 Likes
Try something simple at first: try to brute-force only the nodes that appear on a cycle (as long as the graphs are randomly generated there should be a lot less than N nodes). Note: I haven’t tested this theory.
Both @min_25 and @ceilks have some nice meet-in-the-middle approaches. I’d like to ask both of them to explain their ideas.
BTW: congratulations for your solution. It was by far the nicest written and explained. I know that this doesn’t matter in the overall standings but I really enjoyed reading it.
1 Like
Thanks for the compliment 
For brute force, I have tried doing long long bitmask dfs (with bombed pruning) but unfortunately that gave TLE. As far as I understood @min_25’s approach, it seems he still partly used randomized algo for smallish. I guess random might still be best after all?
1 Like