DCP-399: Jump Minimum Steps Back to All Problems

Hard Divide and Conquer > Dynamic Programming


You are given an array of **n** integers. Currently you are at **m**'th (*1 <= m <= n*) position. It is guaranteed that the value of the *m*'th position is the smallest among the all values in the array. You must visit each **position exactly once**. Each time **you must jump** to the position whose value is equal to the current value. If there is no such position then you have to jump the position whose value is minimum among the non-visited values.In order to jump from position *i* to position *j* you have to add ***|i-j|*** steps with your total steps, which is the absolute difference between index i and j. Initially total steps is 0.You have to visit the full array in such a way that total steps become as small as possible. For example, if there are 5 integers: 2 4 3 1 2 and you are at 4th position (1-indexing) then you can visit the full array it in two ways. Way 1: Position 4 -- position 1 – position 5 – position 3 – position 2. (Total number of steps: 3 + 4 + 2 + 1 = 10) Way 2: Position 4 -- position 5 – position 1 – position 3 – position 2. (Total number of steps: 1 + 4 + 2 + 1 = 8) From the above two cases, we can say that **Way 2** is better than **Way 1** as **Way 2** takes less steps to traverse the full array then **Way 1**. Input: ------ Input starts with an integer *T (**1≤ T≤ 5**)*, denoting the number of test cases. Each case contains two lines. The first line of each test case contains two integers which denote the values of **n** and **m**. The second line of each test case contains **n** space separated integers which denote the values of the array. Output: ------- For each case output should contain the minimum number of steps need to traverse the full array. Constraints: ------- **1 <= T <= 10** **1 <= n, m <= 100000 (m <= n)** **1 <= Values in position i <= 100000 (1 <= i <= n)** Sample Input ------------ 2 5 5 2 3 3 2 1 4 3 1 1 1 2 Sample Output ------------- 6 5


Problem Setter:

Faruk Hossain Milon

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

6/7

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 0.01s
02 Robbinb1993 Cpp14 0.14s
03 Morass Cpp14 0.36s
04 BishalG Cpp14 0.39s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support