CollectBoxes
SRM 854 · 2024-04-24 · by misof
Problem Statement
You are standing on coordinate 0 of the real axis.
Somewhere along the axis there are also N boxes, numbered from 0 to N-1. Initially, box i is located at the integer coordinate B[i]. These coordinates are not necessarily distinct - some boxes may share the same starting coordinate. Arbitrarily many boxes may share the same coordinate at any moment.
Your task is complete when all the boxes are standing on the ground at the same integer coordinate. You have to complete this task as quickly as possible. You get to choose that final coordinate and the specific strategy used to get all the boxes to that coordinate. Only the boxes matter, your final position does not: as soon as all the boxes are at the same coordinate, the task is complete regardless of your position at that moment.
At any moment, you can spend one second to move one step left or right (i.e., increase or decrease your coordinate by 1).
You can also instantly pick up a box that's at your current coordinate or put down the box you are currently carrying. You cannot carry more than one box at the same time.
Calculate and return the minimum time needed to finish your task.
In order to keep the input size small, we will use a pseudorandom array B. Please use the pseudocode below to generate it.
for i = 0 to length(Bprefix)-1:
B[i] = Bprefix[i]
state = seed
spread = bhi - blo + 1
for i = length(Bprefix) to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
B[i] = blo + (state modulo spread)
Notes
- The reference solution does not use the assumption that B is pseudorandom. It would correctly solve the task for any array B of the maximum allowed length.
- The pseudocode used to generate B guarantees that all the generated values will lie between blo and bhi, inclusive. Note that the values in Bprefix may lie outside this range.
Constraints
- N will be between 1 and 500,000, inclusive.
- Bprefix will have between 0 and min(N, 200) elements, inclusive.
- Each element of Bprefix will be between -10^9 and 10^9, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- blo will be between -10^9 and 10^9, inclusive.
- bhi will be between blo and 10^9, inclusive.
2
{11, 10}
0
0
0
Returns: 11
There is a box at coordinate 11 and another at coordinate 10. The optimal solution is to make 10 steps right, pick up the box that's there, take another step right, and put down the box you're carrying.
5
{10, 10, 11, 10, 10}
0
0
0
Returns: 12
Here the optimal strategy is to take 11 steps right, pick up the only box that's at coordinate 11, take a step back, and put the box down.
2
{-10, -11}
0
0
0
Returns: 11
Remember that coordinates of boxes can be negative. This is essentially the same as Example 0 but in the opposite direction.
2
{-47, 47}
0
0
0
Returns: 141
This test case has two optimal solutions: you go to one of the boxes, pick it up and bring it to the other box.
9
{10, 20, 30}
47
-20
100
Returns: 322
Watch out for integer overflow when generating the array B. The array you should get for this example looks as follows: B = {10, 20, 30, 3, 34, 34, 59, -1, 81}.
3
{1000000000, -1000000000, 1000000000}
47
47
47
Returns: 3000000000
Watch out for integer overflow also when computing the answer itself: it does not always fit into a 32-bit variable.
Submissions are judged against all 94 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CollectBoxes with a public method long long collect(int N, vector<int> Bprefix, int seed, int blo, int bhi) · 94 test cases · 2 s / 256 MB per case