NeverSayNever's blog

Help me to solve this problem
By NeverSayNever, 10 years ago, In English

This problem appears in the CodeSprint Elimination Round 2. I request all of you to please explain how to solve this problem.

https://www.hackerrank.com/contests/csindia14-er1/challenges/the-blacklist

I think it requires DP but could not able to come up with a approach.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can set a state [position][mask] as 'The minimum value to kill gangsters from 0 to position using (bits marked as '1' in mask). If you ever solved a dynamic programming with bitmask problem before, this explanation is enough.

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

    I have not solved such kind of dynamic programming problem before. Please provide me link to some source where i can read more about it or some problems link where i can try my hand.

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

      It's essentially an standard dynamic programming solution, you have defined a state, and a relation between then. The difference, is that the second argument in a state (namely 'mask') stores an representation of which mercenaries you already assigned to a task (and due to problem's statement, it cannot be assigned to another one).

      This argument is an integer, if we use the binary representation of this integer, we can assign '1' for used and '0' for not used. With this in mind, we can memorize which mercenaries we already used with a single integer parameter. To set an mercenary as used, we can set the bit with it's index as one, take it as a home work and question yourself "How to change the state of the i-th bit in a integer number ?".

      I've coded an solution for this problem but I haven't tested it because they said it's a restricted contest when I tried to submit it.

      Code

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

        @aajjbb thank you so much and your solution is all correct. I can submit the solution to this problem (i think you did not participated in this contest that's y u cant submit). I got the idea behind your solution.

        in your code DP[i][j] states that to kill the gangster from i to n-1 with the help of shooters which is not selected (j binary representation) what is the minimum expenditure required. Am i right ??

        Can you provide link to the other problems based on the related concept.

        → Reply