rituranjna's blog

How to solve problem 8C .?
By rituranjna, 12 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

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

Please anybody help ..!!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Refer to tutorial for solution

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 !!

      → Reply
»
12 years ago, # |
← 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