Optimal Moves

Practice

4.6 (5 votes)

Dynamic programming

Segment trees

Advanced data structures

Segment tree

Data structures

Problem

87% Success 390 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

There are \(N\) points placed on a number line at position \(1, 2,..., N.\) Initially, you are at point \(1\) and want to find the minimum cost to reach each of the \(N\) points. You are allowed to move only towards +ve x-axis. Let's say, after certain moves, you are at point \(i ( \(\)and want to make the next move. You are allowed to make a move only of the following two types: type \(1:\) by moving to the next point i.e point \(i+1\) which cost \(A_i.\) type \(2:\) by moving to point \(j\) if and only if \(i∈[ L_j, R_j ]\) which cost \(B_i.\) \(\) Find the minimum cost to reach each of the \(N\) points. Input Format The first line contains \(T\) denoting the number of test cases. The description of \(T \) test cases is as follows: Each test case consists of multiple lines of input. The first line of each test case contains one integer \(N\) — the number of points. The second line consists of \(N-1\) space-separated integers denoting the elements of array \(A\). The Third line consists of \(N\) space-separated integers denoting the elements of array \(B\). The Fourth line consists of \(N\) space-separated integers denoting the elements of array \(L\). The Fifth line consists of \(N\) space-separated integers denoting the elements of array \(R\). Output Format For each test case, output on a new line, the minimum cost to reach each of the \(N\) points. Constraints \(1 \leq T \leq 10^{5}\) \(2 \leq N \leq 2\cdot10^{5}\) \(1 \leq A_i, B_i \leq 10^{9}\) \(1 \leq L_i \leq R_i \leq i\) \(\text { It is guaranteed that sum of N over all test cases doesn't exceed }\ 2\cdot 10^{5}\)

Sample Input

2
5
5 3 1 1
4 2 4 1 1
1 1 2 1 3
1 2 2 4 5
6
6 8 5 10 5
7 4 5 3 8 1
1 1 2 2 1 4
1 2 3 4 3 5

Sample Output

0 4 6 4 5
0 6 10 10 7 12

Explanation

Test case 1: You are initially at point \(1\) ( \(cost = 0\) ). The only way to reach point \(2\) is by using move \(1 → 2\). Since, point \(2\) is next to point \(1\) so we can perform the move \(1 → 2\) using move of type \(1\) with the cost of \(A_1 = 5.\) Also, \(1∈[ L_2=1, R_2=2 ]\) so we can perform the move \(1 → 2\) using move of type \(2\) with the cost of \(B_1 = 4.\) Hence, the minimum cost is \(min( 5, 4 ) = 4.\) The only way to reach point \(3\) is by using moves \(1 → 2→ 3\) because we can't move directly \(1 → 3\) since, \(1 ∉ [L_3=2, R_3=2]\). We have already found the optimal way to reach point \(2\) with the minimum cost of \(4\) above. Now, to reach from \(2→ 3\), we again have both types of move possible because point \(3\) is next to point \(2\) and also \(2∈[ L_3=2, R_3=2 ].\) For move \(2→ 3\), move of type \(1\) costs \(A_2 = 3\) and move of type \(2\) costs \(B_2 = 2.\) Hence, the minimum cost is \(4+min( 3, 2 ) = 4+2=6.\)

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Results

Custom Input

Run your code to see the output

Submissions