Editorial:Mr. Pompom & Dragon

Problem Link:

https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-dragon

Difficulty: Moderate

Prerequisites: Basic intuition or Dynamic programming

Problem in short:

There are N kingdoms numbered 1 to N. From i-th kingdom you can go up to (i + arr[i]) th kingdom. (You can choose any kingdom between i and (i + arr[i]) ) Mr Pompom starts from 1st kingdom and wants to reach N-th kingdom. Determine minimum number of kingdoms he will have to traverse to reach N-th kingdom.

Approach 1:Using basic intuition and observation (Range maximizing approach)

Explanation:

Ask yourself a question, where I would like to reach at any kingdom??Answer will turn out to be I want to go farthest kingdom possible as you want to reduce number of steps.

 So at each kingdom’s tunnel, we select a tunnel within the coverage of present tunnel having maximum range, and continue doing the same till the range becomes equal or exceeds the position of last kingdom which is our destination. If there are more than one tunnels with same range then we select the farthest tunnel.

Now we can do some tricks while doing this like if the tunnel which is already taken into consideration in previous case and not chosen, then we won’t check for it another time as it won’t get selected anyway.(Why?)

Implementation (Source Code):

https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-dragon/submissions/code/3544402

Approach 2:Using Dynamic programming

Quick Explanation:

Use dynamic programming approach. Let dp[i] be the minimum number of kingdoms he will have to traverse to reach i-th kingdom. We can calculate dp[i] by (dp[Xi] + 1) , where Xi is minimum index from which we can reach i-th kingdom. The answer to the problem will be dp[n-1].

Explanation:

We will use dynamic programming to solve problem. Let dp[i]=minimum number of kingdoms needed to traverse to reach i-th kingdom.(Here 0-indexing is used)

dp[0]=1;

So we will start looping from 0-th kingdom to N-1-th kingdom(0 -indexing) and keep assigning dp[] to all such remaining vertices that can be reached from that kingdom as dp[j]=dp[i]+1. We will break the Loop when no kingdoms are left. In each loop we will keep track of index from which kingdoms are remaining. Thus answer will be dp[n-1].

Pseudo code

read(n)
for (i=0;i<n;i++)

read(arr[i]);

dp[0]=1;

startKingdom=1;

for(i=0;i<n;i++)
{
for(j=startingKindom;j<=(i+arr[i]) && j<n;j++)

{
dp[j]=dp[i]+1;

}
startKingdom=j;
if(startKingdom>=n) break;

}

print dp[n-1];

Link to Solution(Code)  using DP approach:

https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-dragon/submissions/code/3538715

Time complexity analysis:

Both approaches have same time complexities of O(N). But as Dynamic Programming approach uses much memory it slightly takes more time than Range-Maximizing approach. Nevertheless both approaches are fast enough to pass out all the test cases.

NOTE:There is another possible acceptable solution which runs in O(nlog(n)) time complexity using bottom-up DP and segment tree.

Modification of question in which dp becomes much useful:

Suppose the position of firesafe bunker wasn’t fixed but changes in each query asked then in this case the answer would be directly dp[query]. Here, storing intermediate values by dynamic programming approach enables us to answer the query in O(1).

Authors:

Suparshva Mehta & Aayush Kapadia

Advertisements

Questions on Dynamic Programming!

Easy

1) http://www.codechef.com/problems/COUPON

2) http://www.codechef.com/problems/SPIDY2/

3) http://www.spoj.com/problems/GNYR09F/

4) http://www.spoj.com/problems/PERMUT1/

5) http://www.spoj.com/problems/SQRBR/

6) http://www.spoj.com/problems/JEDNAKOS/

7) http://codeforces.com/contest/467/problem/C

Medium :

1) http://www.spoj.com/problems/FARIDA/

2) http://www.codechef.com/problems/COINS

3) http://www.spoj.com/problems/BEHAPPY/

4) http://community.topcoder.com/stat…

5) http://www.codechef.com/problems/DELISH

6) http://www.codechef.com/problems/FROGV/

7) http://www.spoj.com/problems/EDIST/

8) http://www.spoj.com/problems/WACHOVIA/

9) http://codeforces.com/contest/455/problem/A

10) http://www.spoj.com/problems/MFISH/

11) http://www.codechef.com/problems/LEPAINT/

12) http://www.codechef.com/problems/SEATSR/

13) http://www.spoj.com/problems/INS14E/

14) http://www.spoj.com/problems/MARTIAN/

15) http://community.topcoder.com/stat…

16) http://www.codechef.com/problems/LEBLOCKS

17) http://www.codechef.com/problems/LEMOVIE

18) http://www.codechef.com/problems/LEMAGIC

19) http://www.codechef.com/problems/LECOINS

Advanced Dynamic Programming

For Reading

Commonly Used DP state domains : http://apps.topcoder.com/forums/…

General Aspects of DP : http://apps.topcoder.com/forums/…

Optimizing DP solutions : http://apps.topcoder.com/forums/…

Dynamic Programming Optimizations

Convex Hull Trick 1 : http://wcipeg.com/wiki/Convex_hull_trick

Problem(s) : http://codeforces.com/contest/319/problem/C

Divide and Conquer Optimization :

http://codeforces.com/contest/321/problem/E

https://www.hackerrank.com/…/chall…/guardians-lunatics-ioi14 (Solve problems with the help of editorial to learn)

Convex Hull Trick 2 : http://apps.topcoder.com/forums/…

Problem(s) : http://www.spoj.com/problems/NKLEAVES/

http://codeforces.com/contest/311/problem/B

Digit DP

http://stackoverflow.com/…/how-to-count-integers-…/22394258…

http://codeforces.com/blog/entry/8221

Problem(s) : http://www.codechef.com/problems/ANUBGC

http://www.spoj.com/problems/LUCIFER/

http://www.spoj.com/problems/RAONE/

http://www.spoj.com/problems/GONE/

DP on trees

http://www.iarcs.org.in/…/online-study-…/topics/dp-trees.php

Problem(s) : http://www.spoj.com/problems/PT07F/

https://www.spoj.pl/problems/PT07X/

http://www.spoj.pl/problems/VOCV/

Bitmask DP

http://community.topcoder.com/tc…

Problem(s) : http://www.codechef.com/problems/TSHIRTS

http://usaco.org/index.php?page=viewproblem2&cpid=515

http://www.spoj.com/problems/HIST2/