Hello All,
I am very new to the concept of dp with bitmasking. So, was going through some basic problems like this. My code's link is this: http://ideone.com/kerT7s . I have precalculated the distance between every restaurant location and the solitairs location. Then because we have the constraint of limited number of restaurants (n), my lowest number with n bits set is (1<<n)-1 . The next number will be the one with same number of set bits. Then corresponding to every set bit (which denotes the location of the restaurant), I am checking the distances of each solitiare if it lies within the permissible radius range.
But the above gives TLE. I have no clue why, someone please give some hint or point out the flaw. Will be really helpful. Thanks :)
While you precompute the distances, you can store the number of solitairs that can be reached from every location, like building a graph, instead of checking with every solitaire during the brute force part.
To check if you have visited a solitaire previously, you can use this trick:
Instead of using a boolean-like mark (1 visited, 0 otherwise) you can mark with an integer. Suppose you are in the iteration i of the brute force, you can check if a solitaire K is already visited with visited[K] == i. If not, update it with i. This will remove the initialization cycle of the visited array in every iteration of the brute force :)
And you don't need to use floats in this problem. Remember that you need to know if some solitaire is inside the radius, not the distance itself :D just remove the square root from the euclidean distance equation by squaring
Hope this helps!
Your suggestion of storing the possible reachable solitairs from a particular location of restaurant worked ( http://ideone.com/bhjTYZ ) Possible because the iteration for the loop of variable 'K' are now reduced to the size of vec[j] (j refers to the location) now.
Thanks a ton :)