FUNKVAL - Editorial

FUNKVAL - Editorial by Satwant Rana

Given small problem size, this problem can be solved in exponential time.

A simple solution that won’t accept is traversing over all possible subsets of nodes, and add the funk value of this subset to the net result. The time complexity is O(2^n n^2).

Naive Solution Link.

We can now use dynamic programming to calculate the funk value for every subset in O(2^n n). Although this will pass, it takes O(2^n) memory. We can improve upon this by augmenting the previous naive solution.

Instead of traversing the set of nodes in the order 0 to 2^n - 1, one can access them in the gray code order. This way two consecutive subsets during iteration will have exactly one bit different. Thus we can get the answer to current subset by making O(n) operations on asnwer of last step.

Model Solution Link.