### rituranjna's blog

By rituranjna, 9 years ago,

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

• -3

 » 9 years ago, # |   -7 Please anybody help ..!!
•  » » 9 years ago, # ^ |   0 Refer to tutorial for solution
•  » » » 9 years ago, # ^ |   0 Abe hagode .!! What could i found is this editorial and in this blog , solution for only D & E is published . If you are talking about another tutorial ,please let me know !!
 » 9 years ago, # | ← Rev. 6 →   +7 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).
•  » » 9 years ago, # ^ |   +3 Thank You diego_v1 :)