NPLQLC - Editorial

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Aniket Marlapalle

Tester: Harsh Shah

Editorialist: Aniket Marlapalle

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

DP, Dijkstra’s Algorithm

PROBLEM:

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.

EXPLANATION:

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.
As the number of distinct colors of the buildings is less than 10 we can represent any combination of it using a mask of integers from 0 to 1024.

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

2

@admin- Must have spent good hours for editing XD