Member Count: 483,217 - May 18, 2013  [Get Time]

 Problem Statement

Problem Statement for CucumberWatering

Problem Statement

Cucumberman planted N cucumbers along a straight road. Cucumbers are numbered 0 through N-1, and the position of the i-th cucumber is x[i]. The cucumbers are at pairwise distinct coordinates, but their coordinates are not necessarily in sorted order. He waters all cucumbers every day. He can't change the order of watering cucumbers, so he must water cucumber 0 first, water cucumber 1 next, and so on. (Note that this means he may be going back and forth along the road.)

Watering a cucumber takes zero time. When walking, Cucumberman needs one unit of time to travel one unit of distance. Additionally, he can build at most K teleports at any positions (including non-integer ones). If there are teleports at both P and Q, he can move from P to Q instantly using teleports.

He wants to minimize the duration between watering cucumber 0 and watering cucumber N-1. Return this minimum time, assuming that he builds and uses the K teleports optimally.

Definition

 Class: CucumberWatering Method: theMin Parameters: int[], int Returns: long Method signature: long theMin(int[] x, int K) (be sure your method is public)

Constraints

-x will contain between 2 and 50 elements, inclusive.
-Each element of x will be between -1,000,000,000 (-10^9) and 1,000,000,000 (10^9), inclusive.
-Elements of x will be pairwise distinct.
-K will be between 1 and 50, inclusive.

Examples

0)

 `{0, 6, 8, 2}` `2`
`Returns: 6`
 One optimal way is as follows: Build teleports at 1 and 7. Water cucumber 0 at 0. Walk to 1, teleport to 7, walk to 6 and water cucumber 1. Walk to 8 and water cucumber 2. Walk to 7, teleport back to 1, walk to 2 and water cucumber 3. It takes |0-1| + |7-6| + |6-8| + |8-7| + |1-2| = 6 unit time in total.
1)

 `{-1000000000, 1000000000, 0}` `1`
`Returns: 3000000000`
 Only one teleport is useless.
2)

 `{58, 2012}` `50`
`Returns: 0`
3)

 `{9, -3, 14, 6, 5, -9, 32, 7, -5, 26, 2, 11}` `3`
`Returns: 58`

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:
2012 TCO Algorithm Round 2A - Division I, Level Two

 Home  |   About TopCoder  |   Press Room  |   Contact Us  |   Careers  |   Privacy  |   Terms Competitions  |   Cockpit Copyright TopCoder, Inc. 2001-