Connection Status:
Competition Arena > PlumbersCoins

PlumbersCoins

TCO14 Round 3A · 2014-03-26 · by vexorian

TCO14 Round 3A · 2014-03-26 · by vexorian · Brute Force, Simulation
Class Name: PlumbersCoins
Return Type: int
Method Name: minTime
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 334 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PlumbersCoins with a public method int minTime(vector<int> tubes, vector<int> coins) · 334 test cases · 2 s / 256 MB per case

Submitting as anonymous