Break the adjacency

3.5

2 votes
2D dynamic programming, Algorithms, Dynamic Programming
Problem

Alex on his walk to Forest of leaf discovers N sticks lying in front of him. Each stick has two values represented by two arrays arr and price of size N where in array arr, arr[i] (0<=i<=N1) denotes length of ith stick and array price, price[i] (0<=i<=N1) denotes price to increment length of ith stick by 1 unit.

Alex calls an array Broken Adjacency when none of the adjacent sticks has equal length. A stick i is adjacent to stick i1 (if any) and stick i+1 (if any). He wants to find the minimum cost to achieve Broken Adjacency. To do so, in 1 move he can increment the length of any ith stick by 1 unit at the price of price[i].

Can you help him find the minimum cost to achieve his goal?

Input Format:

  • The first line contains an integer T denoting the number of test cases.
  • The first input line of each test case contains one integer N, denoting the number of sticks found.
  • The second line contains N space-separated integers denoting the elements of array arr.
  • The third line contains N space-separated integers denoting the elements of array price.

Output Format:

Print the minimum cost to make given sticks to Broken Adjacent sticks.

Constraints:

1<=T<=10

1<=N<=105

1<=arr[i]<=109

1<=price[i]<=109

Sample Input
3
3
2 2 3
100 1 10
3
3 3 4
5 1 10
4
1 2 3 4
4 10 1 1
Sample Output
2
2
0
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1, 
Alex will increment 2 (i = 1) by 2 units and the final array will look like [ 2, 4, 3 ]. The total cost of this operation will be 2. Alex cannot achieve a lower cost than 2.

For test case 2,
Alex needs to increment the length of stick 3 (i = 1) by 2 units. The final array will look like [ 3, 5, 4 ] , the total cost equals 2.

For test case 3, 
The sticks are already Broken Adjacent.

 

Editor Image

?