NarrowPassage
TCO14 Round 2A · 2014-03-26 · by rng_58
Problem Statement
Inside the passage there are some wolves. You are given two
The passage is so narrow that wolves cannot pass by each other. In other words, the relative order of the wolves cannot change while they are in the passage. Luckily, there is a lot of empty space on each end of the passage. If some wolves reach the same end of the passage, they can change their order arbitrarily before reentering the passage.
All wolves must finish at their desired coordinates. Return the minimum total distance the wolves have to travel within the passage in order to reach their final configuration. Note that the distance traveled while they are reordering at the ends of the passage does not count.
Constraints
- L will be between 2 and 1,000,000, inclusive.
- a and b will each contain between 1 and 50 elements, inclusive.
- a and b will contain the same number of elements.
- Each element of a and b will be between 1 and L-1, inclusive.
- Elements in a will be pairwise distinct.
- Elements in b will be pairwise distinct.
5
{1, 2}
{3, 4}
Returns: 4
We have two wolves. One of them wants to go from 1 to 3, the other one from 2 to 4. They can do this without passing each other. (For example, they can both move simultaneously. Alternately, wolf 1 can move before wolf 0 does. There are no restrictions on the movement of wolves other than they cannot pass each other within the passage.) The total distance traveled in this case is |1-3| + |2-4| = 4.
10
{3, 9}
{8, 6}
Returns: 14
One of the optimal ways looks as follows: Wolf 1 moves from 9 to 10. Wolf 0 moves from 3 to 10. Wolf 1 moves from 10 to 6. Wolf 0 moves from 10 to 8.
265467
{133548, 103861, 29821, 199848, 92684, 219824, 215859, 62821, 172409, 109235,
38563, 148854, 24742, 174068, 205005, 75922, 87316, 5542, 57484, 40792,
25229, 152216, 21547, 22203, 84712, 231522, 235703, 184895, 100787, 174440,
156904, 84898, 185568, 108732, 260098, 89488, 221604, 104555, 165775, 90444,
81952, 149671, 209674, 22185, 45420, 41928, 16098, 65324, 90870, 35243}
{150289, 135139, 69841, 227226, 177427, 230314, 199175, 81572, 220468, 151049,
40009, 145963, 115246, 252932, 263651, 38434, 120096, 69576, 29789, 115046,
33310, 260771, 5723, 80733, 107864, 142447, 235490, 242149, 124564, 134602,
245962, 7078, 215816, 219864, 190499, 210237, 212894, 142760, 126472, 201935,
119308, 120211, 235235, 19446, 87314, 17286, 61990, 102050, 261812, 257}
Returns: 7148670
1000000
{706292, 756214, 490048, 228791, 567805, 353900, 640393, 562496, 217533, 934149,
938644, 127480, 777134, 999144, 41485, 544051, 417987, 767415, 971662, 959022,
670563, 34065, 518183, 750574, 546576, 207758, 159932, 429345, 670513, 271901,
476062, 392721, 774733, 502586, 915436, 120280, 951729, 699859, 581770, 268966,
79392, 888601, 378829, 350198, 939459, 644983, 605862, 721305, 269232, 137587}
{322468, 673534, 83223, 551733, 341310, 485064, 885415, 927526, 159402, 28144,
441619, 305530, 883149, 413745, 932694, 214862, 677401, 104356, 836580, 300580,
409942, 748444, 744205, 119051, 999286, 462508, 984346, 887773, 856655, 245559,
418763, 840266, 999775, 962927, 779570, 488394, 760591, 326325, 206948, 13999,
285467, 401562, 786209, 169847, 171326, 2901, 296531, 572035, 364920, 939046}
Returns: 45670501
744827
{415046, 553660, 8114, 632319, 34961, 231982, 664471}
{447751, 427206, 443068, 480542, 732290, 521646, 608103}
Returns: 4226419
Submissions are judged against all 273 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NarrowPassage with a public method int minDist(int L, vector<int> a, vector<int> b) · 273 test cases · 2 s / 256 MB per case