This problem is brought to us by our colleague Clive Fraser aka CSFPython - thanks a lot!
Two trains arrived at the main station of Chaipur city, from where they are to proceed to Rhotinagar.
However one of the two locomotives is electric, the other old good steam engine - and the railroad further
is not electrified yet. In short, trains need to be merged and hauled from here by the steam engine alone.
Unusual implication is voiced by train guards - they want to run over the roofs of the moving train from time to time and check everything is all right. As the cars of the train are of different heights, guards want them to be merged in such way that sum of height differences between cars is minimized. (if you ever enjoyed jumping between the car roofs of the moving train, you readily understand their motivation)
For example, suppose two trains are of 5 cars each, and their heights (say, in inches) are respectively:
trainA = [61, 89, 45, 71, 93] trainB = [52, 73, 72, 85, 3]
Obviously the sum of jump heights is minimizied if cars are simply sorted, for example:
93, 89, 85, 73, 72, 71, 61, 52, 45, 3
This would give sum of height differences simply equal to 90. But railroads do not work that way!
Surely: while merging of two trains is trivial operation at any junction, but we do not usually change the order of cars of the same train! Such operation though theoretically possible, requires many more runs back and forth, coupling and uncoupling cars.
Optimal merging with the cars order preserved:
61, 89, 45, 52, 71, 73, 72, 93, 85, 3
This gives "jump heights" totalling to:
28 + 44 + 7 + 19 + 2 + 1 + 21 + 8 + 82 = 212
Problem Statement
For simplicity, both trains have the same number of cars N - and that is small, not exceeding 15.
The goal is to tell minimal sum of "jump heights".
Input data:
First line gives the number of testcases.
Then testcases follow, each consisting of 3 lines.
- line with single value N - length of both trains;
- two lines describing heights of cars of two trains.
Answer: should tell minimal sum for every testcase.
Example:
input:
3
2
61 89
52 73
3
61 89 45
52 73 72
5
61 89 45 71 93
52 73 72 85 3
output:
37 81 212
Please do not be surprised with 5-digit height values - in the age of innovations heights are measured
to the 1/1000 of an inch!