CucumberWatering
TCO12 Round 2A · 2012-03-27 · by rng_58
TCO12 Round 2A · 2012-03-27 · by rng_58 · Dynamic Programming, Math
Problem Statement
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.
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.
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)
{563581185, -912574337, 985630444, 944054128, 944618546, 87797719, -589263075, -486770822, 140860384, 992497371, 601121303, 198517030, -873735957, 473167534, -423088531, 735430961, -333194220, -323972182, -132629221, 344971795, -919730741, -656891687, 66834114, -94484082, 255270988, -135329180, -49604093, 374045844, -154912016, -359106606, -716933750, -484513488, 77795978, 947136787, -526862721, 950949696, -430224443, 959507535, 430758812, -808685434, -445457558, -664262316, 919297508, 754682875, -312857865, 536933516, 597134796, 126412801, -174155788, 794009029}
1
Returns: 33502319560
1)
{-485419501, 869992369, -237766831, -536692389, 587917460, -724559331, 165037606, -237315266, 379784329, -762332332, 36584326, -348342877, -324203280, 121982811, 745436682, -408401971, -770873170, -623866964, -743993184, 447999658, 655140981, 832021770, -899092739, 940920896, 519872561, -235259365, 987281, -576059810, -912995787, 684161129, 357569150, -212923458, 340007420, -392843948, -333464533, -185197708, -438253069, -512405373, 474896293, -114986051, 207049741, 781811135, -528800398, 883537430, 459635399, -836994604, 963298347, -113930922, -153493438, -484278794}
2
Returns: 18116173390
2)
{561206548, 7234155, -716513749, -333174897, 936823177, 853209019, -771070991, 918561948, -69468298, -235399873, -177674218, -119773414, 676882087, -338249127, -552577592, 543310195, 620606368, -322500206, 901730462, -934940898, 428597285, 818695150, 199916880, -799521660, 862567427, -35884847, 532644666, -924710864, 760335143, -52305265, 320091929, -927662424, -409342256, 972231172, -916503632, 148520444, 595036221, 682081139, -385861529, 998698964, 597928293, 949669675, 785801284, -954494860, -442980922, -621916170, -466617114, -904964116, -27809773, -939591003}
3
Returns: 12831249911
3)
{-609385316, -1870473, 559280880, 131525681, -121229139, 756120592, -648521431, -855057072, 973522069, 504589280, 505566759, 519311896, -341358410, 433880722, 205828120, -796094274, -428516896, 690450926, -879810652, 82569966, -991461513, 366138641, -432710882, -659661914, 93193004, 409033113, -975132050, -921445483, 49240909, -595131270, -934871111, -636849785, 318770994, -83619307, 332611547, -185864444, 558611427, 969664446, 683970543, 235399434, -690175503, -602516804, 474971038, 454766805, -472347700, 859043508, 722788359, -539320419, -798266908, -848767984}
4
Returns: 10104433375
4)
{-224794679, 207331537, -486984974, -867766451, -882561446, 544615266, 765128446, 103210114, -316161461, 985446114, 697071248, 630346789, -523064221, 686706528, 225923275, -499427497, -743448856, -893806140, -652858649, -350081005, 709424641, 824679571, -473862941, 65270950, -29195605, -624717449, -66823475, -109976769, -911858230, 64998726, 125862564, -338038167, 863533900, 686767398, -467448607, -173839645, 559913685, -576822558, -929153824, -2611428, 802139908, 464062258, -912963099, -280389183, 516634158, -934928114, -290023958, 229291848, 861098721, -138241926}
5
Returns: 7241232579
18)
{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.
19)
{-1000000000, 1000000000, 0}
1
Returns: 3000000000
Only one teleport is useless.
Submissions are judged against all 89 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CucumberWatering with a public method long long theMin(vector<int> x, int K) · 89 test cases · 2 s / 256 MB per case