Dynamic programming with bit masking.

general
, ,
1

I am attempting to solve ASSIGN on spoj. It’s a simple dp+bitmask problem. I tried solving it recursively but for some reason I keep getting TLE.

Help me figure out if I can further optimize my code to reduce its time complexity or if it can only be solved iteratively.

My solution - my solution

Time complexity - O(Number of test_cases * n * 2^n)

Space Complexity - O(n*2^n + n^2)

2

Your problem link leads to ideone. Please edit it so that it leads to the SPOJ question.

1 Like
3

It go accepted now. It seems when I was using pow(x,y) which was TLE but without it its AC.
Thanks anyway.

1 Like