Stampede | Practice Problems

Stampede

★★★★★

5 votes

Algorithms, Medium, Dynamic Programming, Dynamic programming

Details

Submissions

Discussion

Editorial

Problem

The annual bull racing has started and the raging bulls are finishing off to the finishing line. Jimmy decides to cross the finish line by riding on the bulls. Jimmy is at position $0$ at the start time i.e time= $0$ .Initially the position of the bulls on a straight line track is given as an array $P$ . On the straight path, there are $N$ lanes (one for each bull) and no bull can change the lane in between.

Also, each bull is racing with a constant speed, given by the array $S$ (speed is in units per second ). Each bull is invisible initially and becomes visible at different times denoted by array $ST$ i.e for a bull $i$ it becomes visible at time $ST_i$ at its position given by $P_i$ . The maximum time interval for which a bull can carry Jimmy is given by an array $CT$ ( time is in seconds ).

Jimmy has to jump over to a different bull before the maximum carrying time of that bull is reached. Jumping over the next bull requires negligible time. Also, Jimmy can change the bull only if it is at same position ( although it can be on a different lane) as the current bull.

For a given destination $K$ units apart from the initial point, help Jimmy to find minimum number of bull changes to reach the given destination. It is given that the transitions can happen only at integer time units.

Note: Jimmy can only make direct jumps from one bull to another and cannot jump on the ground at any instant. However, at initial position $0$ he can stay for as much time as he wants.

INPUT FORMAT

First line contains an integer $T$ denoting the number of testcases
First line of each testcase contains an integer $N$ , denoting the number of bulls and $K$ denoting the final destination( distance from the initial position of Jimmy which is 0 )
Each of the next $4$ lines of each testcase contains $N$ space separated integers denoting the arrays $P$ , $S$ , $ST$ , $CT$ respectively

OUTPUT FORMAT

Output single integer denoting the minimum number of bull changes or -1 if is not possible

CONSTRAINTS

$1 \leq T \leq 100$
$1 \leq K \leq 1000$
$1 \leq N, S_i, CT_i \leq 10$
$0 \leq P_i , ST_i \le K$

SUBTASKS

For 10 Points : $1 \le K \le 10$
For 90 Points : Original Constraints

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the first testcase its impossible to reach the final destination, hence the ans is -1.

For the second testcase, Jimmy jumps to bull 3 at time=0 units at position 0. He jumps to bull 1 at time=1 units at position 1. He again jumps to bull 3 at time=2 seconds and keeps switching between 1 and 3 till he reaches the position 10. Hence the switches occur at positions 1,2,3.....9. Hence the answer is 9.