Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Aniket Marlapalle
DP, Dijkstra’s Algorithm
Given a row of buildings where you need to go from building number S to T with jumping no more than k buildings at a time and using at max some given no of distinct colors of buildings you can use, minimize the cost.
In the given problem Batman has to go from building S to T and can go from ith building to any building between (i-k) to (i+k). From this lets first make following 2 conclusions:
- The cost of going from S to T is same as going from T to S. So without loss of generality lets assume S < T.
- He will not get any benefit by going backwards so lets assume he always moves forward.
Now we can write a recursive function with 2 parameters, fun(i, mask) with i being the building Batman is currently standing at and mask being the current mask of colors.
Now from the ith building we will make transitions to buildings i+1 to i+k with appropriately changing the mask. Finally if the number of bits in the mask is less than the given number then accept this cost.
Alternatively, neglecting the second fact of Batman not going backwards, you can also use Dijkstra’s Algorithm with the same parameters.(Please see the Author’s solution for more clarity).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here