JOIN
Get Time

   Problem Statement  

 Problem Statement for PlumbersCoins

Problem Statement

    It is a known fact that plumbers can travel through tubes as if they were teleports. Often you can see a plumber entering a tube and then, just a second later, emerging from its other end. It is also a known fact that plumbers love coins. Our plumbers, tubes, and coins all exist in the same one-dimensional world.



You are given two int[]s: tubes and coins. Each of them is sorted in increasing order. The int[] tubes has an even number of elements. For each valid i, there is a tube with endpoints at the coordinates tubes[2*i] and tubes[2*i+1]. The plumber can enter either end of any tube and teleport to its other end in one second. The plumber can also move by walking. His walking speed is one unit of distance per second. The int[] coins contains the coordinates of all coins. The plumber must collect all coins by visiting their coordinates. Collecting a coin takes no time. Coins can be collected in any order.



The plumber's initial coordinate is 0. Return the minimum time the plumber needs to collect all the coins.
 

Definition

    
Class:PlumbersCoins
Method:minTime
Parameters:int[], int[]
Returns:int
Method signature:int minTime(int[] tubes, int[] coins)
(be sure your method is public)
    
 

Constraints

-tubes and coins will contain between 1 and 50 elements, inclusive.
-tubes will contain an even number of elements.
-Each element of tubes and coins will be between 1 and 1,000,000,000 (10^9), inclusive.
-All elements of tubes will be distinct and sorted in increasing order.
-All elements of coins will be distinct and sorted in increasing order.
-Tubes and coins will never share the same position.
 

Examples

0)
    
{2, 20}
{3, 4, 18}
Returns: 9
The optimal solution looks as follows:
  • The plumber walks to coordinate 3. (This takes 3 seconds.)
  • The plumber collects coin #0. (This takes 0 seconds.)
  • The plumber walks to coordinate 4. (This takes 1 second.)
  • The plumber collects coin #1. (This takes 0 seconds.)
  • The plumber walks to coordinate 2. (This takes 2 seconds.)
  • The plumber enters the tube and travels from tubes[0]=2 to tubes[1]=20. (This takes 1 second.)
  • The plumber walks from coordinate 20 back to coordinate 18. (This takes 2 seconds.)
  • The plumber collects coin #2. (This takes 0 seconds.)
The total time is 3+1+2+1+2 = 9 seconds.
1)
    
{10, 20, 30, 40}
{15, 39}
Returns: 32
The plumber walks to coordinate 30 (and grabs coin #0 along the way). Then he teleports to coordinate 40 and walks to coordinate 39 to grab the other coin.
2)
    
{1, 105, 106, 119, 120, 200}
{117, 121}
Returns: 10
The plumber can reach coordinate 119 in 4 seconds. Then, he can walk to 121, collect coin #1, walk back to 117, and collect coin #0. Note that he is not required to collect the coins in the order in which they are given in the input.
3)
    
{5,13}
{7,8,14}
Returns: 12
4)
    
{1, 7000000}
{10, 100, 1000, 1000000, 6000000, 7000001}
Returns: 3000002
5)
    
{11990077,86497123,155806046,182547019,423754766,514490485,540050520,562549306,569114639,952908416}
{361042502,497737263,510014274,529291145}
Returns: 368861292

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2014 TCO Algorithm Round 3A - Division I, Level Three