rituranjna's blog

How to solve problem 8C .?
By rituranjna, 13 years ago, In English

I am stuck on 8C .Can anyone suggest me how to solve this problem ..?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

Please anybody help ..!!

→ Reply
»
13 years ago, hide # |
← Rev. 6  
Vote: I like it +7 Vote: I do not like it

Like the tags of the problem indicate, it's solved by using bitmasks and DP.

  • The state of the DP is the objects put in the handbag so far. You represent these using bitmasks (objects have to be 0-indexed). For example, if you've put objects 0, 3 and 5, the state is 41 (20 + 23 + 25). The size of the DP array will then be 224.
  • Iterate through all the states from 0 to 2N - 1 seeing if adding one or two objects to this state yields a better solution than what you currently have. The cost of adding two objects i and j (potentially the same) is Dist[H][i] + Dist[i][j] + Dist[j][H], where H is the handbag. Dist[i][j] = (x[i] - x[j])2 + (y[i] - y[j])2. Cost[i][i] = 0, obviously.
  • One key observation to make it run in time is that the order in which you put the objects doesn't matter. For example, if the optimal solution is 0 4 3 0 1 0 2 0, it will be the same as 0 1 0 3 4 0 2 0 and the same as 0 1 0 2 0 3 4 0. So, for every state, only consider adding the first object that hasn't been added yet (and maybe another one together with it).
  • To reconstruct the optimal "path", when you find that you can reach state 'y' from state 'x' with optimal cost, store that in an auxiliary array (i.e., From[y] = x).
→ Reply