Problem D2: Line of Delivery (Part 2) Link
Hello everyone, I'd like to talk about Problem D2 from the recent Meta Hacker Cup 2024 Practice Round. The solution suggests that we can use a treap data structure to efficiently handle the operations described in the problem.
Operation 1) Insert a stone at $$$E_i^{th}$$$ empty position.
Operation 2) Move all stones to the left of the inserted stone by 1 unit in the negative direction.
Yes, treaps can be used to solve this problem, but I’ve come up with a simpler solution using a vector approach. Let's maintain an array called emptyPlaces that stores information about all the empty spots. In this array, I track how many balls are located immediately to the right of each empty position. Additionally, I keep a start pointer to mark the current starting position in the array.
So the above 2 operations can be modified as follows:
Operation 1) empty_places[start + E_i - 1]++;
Operation 2) start++;
Example:
Here in this case, the emptyPlaces array looks like $$$[1,2,1,0,0]$$$
Just maintaining these could get me all the distinct positions of the final balls, and since the thrown balls are in order toward the negative x direction, finding the position of each ball is relatively easy.
