Блог пользователя damn_me

Автор damn_me, 9 лет назад, По-английски

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 :)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 :)