CHAND - EDITORIAL

editorial
, ,
1

PROBLEM LINK:

Practice: CHAND Problem - CodeChef
Contest: CodeChef: Practical coding for everyone

Author: [Aditya Pusalkar] adityapusalkar | CodeChef User Profile for Aditya Pusalkar | CodeChef
(Tester and Editorialist)

DIFFICULTY:

Easy-Medium.

PREREQUISITES:

Dynamic Programming.

PROBLEM:

Given N platforms and M of them are unsafe, Chase has to cross all of the platforms in order. We have to find the minimum cost of using a certain set of spells with different costs to make the platforms safe and cross them all, by using 4 types of spells which make the next 1,7,14 and 30 platforms safe respectively.

QUICK EXPLANATION:

This is linear Dynamic Programming Problem, where the minimum cost till the platform i, 1 \leq i \leq N will be equal to the minimum of the costs till the platforms i-1, i-7, i-14, and
i-30 added with the respective costs of spells, if the platform i is unsafe, else just the minimum cost till the previous platform (i-1). We will iterate from i = 1 to N and our final answer will be the minimum cost till platform N.

EXPLANATION:

To cross all the platforms safely, we have to make sure that each platform has been made safe. Once the last unsafe platform has been made safe, Chase doesn’t need to use any more spells. We have been given the costs of all 4 spells in the input, let’s name the array costs. Let the array denoting the unsafe platforms be named platforms.
We know that if we use any spell at a given platform the current platform along with certain extra platforms will be made safe. Being greedy will not get us the correct answer by simply checking the gaps between the unsafe platforms. We have to find the optimal answer using Dynamic Programming. Let us setup our dp array dp as follows, with following logic:

Cost at i th stage: min(dp[i-1]+costs[0], dp[max(0,i-7)]+costs[1], dp[max(0,i-14)]+costs[2], dp[max(0,i-30)]+costs[3])
Cost at initial stage: (dp[0] = 0)

We make sure that at each stage we consider all the possibilities of usage of spells which might make the cost minimum. If we use the first spell we need to check the previous platfrom, if we use the second spell we check the 7 th platform before the current one, if we use the third spell we check the 14 th platform before the current one, if we use the fourth spell we check the 30 th platform before the current one. Using the above DP statement we make sure that we use all available options and also stay in bounds 0-N.

TIME COMPLEXITY:

The time complexity for the above solution is O(N).

SOLUTION:

Setter's Solution 
for i in range(int(input())):
    M,N = map(int,input().split())
    platforms = list(map(int,input().split()))
    costs = list(map(int,input().split()))
    dp = [0 for i in range(platforms[-1]+1)]
    ind = 0
    for i in range(1,platforms[-1]+1):
        if(platforms[ind]==i):
            dp[i]=min(dp[i-1]+costs[0],dp[max(0,i-7)]+costs[1],dp[max(0,i-14)]+costs[2],dp[max(0,i-30)]+costs[3])
            ind+=1
        else:
            dp[i]=dp[i-1]
    print(dp[-1])
1 Like