The fastest way through two assembly lines
Reported in interviews at (where)
A factory builds a car in n stations, one after another, and has two assembly lines that each have all n stations. Station j takes a1[j] minutes on line 1 and a2[j] minutes on line 2.
Getting the car onto line 1 at the start takes e1 minutes, onto line 2 e2 minutes. Taking it off after the last station takes x1 minutes from line 1 and x2 from line 2.
After station j (every station but the last), the car can stay on its line for free, or move to the other line for the next station: from line 1 that takes t1[j] minutes, from line 2 t2[j] minutes.
For each factory, find the fewest minutes in which a car can get on, through all n stations and off again.
Input
The first line holds T, the number of tests. Each test is six lines: n; then e1 e2 x1 x2; then the n numbers of a1; then the n of a2; then the n - 1 of t1; then the n - 1 of t2. Stations are listed first to last.
Output
For each test, one line: the fewest minutes through its factory.
- Input
2
3
2 4 3 2
7 9 3
8 5 6
2 3
2 1
2
1 1 1 1
1 100
100 1
5
5- Output
23
9
- On at line 1 (2) for station 1 (7), across to line 2 (2) for station 2 (5), back to line 1 (1) for station 3 (3), then off (3): 23.
- Start on line 1 and pay 5 to switch after station 1: far quicker than either slow station.
Limits
1 <= T <= 1002 <= n <= 100000the n of all the tests add up to at most 400000every number of minutes is 1 to 10000
Hints
Hint 1
Let f1 be the fastest time to finish station j on line 1, and f2 the same on line 2. Each depends only on the two values for station j - 1.
Hint 2
Station j on line 1 is reached from line 1 for free or from line 2 at the cost of moving: f1 = a1[j] + min(f1, f2 + t2[j - 1]), and the same the other way round. Add the exit times at the end.
Where this was reported
- Societe Generale, SDE on-campus interview, 2021 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
