Meta Hackercup Practice D2 problem

Revision en5, by Ashwanth.K, 2024-09-24 13:02:09

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 + Ei - 1]++; (0-based indexing)
Operation 2) start++; Just moving the start pointer can handle the shifting case mentioned in operation 2) above.

The key advantage of this approach is that we shift the stones to the left of the newly inserted stone by 1 unit in the negative direction. This can be visualized as adding an empty spot to the left of the inserted stone and removing the first empty position from the array.

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.

Code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English Ashwanth.K 2024-09-24 21:02:45 109
en7 English Ashwanth.K 2024-09-24 21:00:32 1004 Tiny change: ' \n\nExample: ' -> ' \n\n#### Example: '
en6 English Ashwanth.K 2024-09-24 14:23:13 3 Tiny change: ') `empty_places[star' -> ') `emptyPlaces[star'
en5 English Ashwanth.K 2024-09-24 13:02:09 1 Tiny change: '[start + E_i - 1]++;`' -> '[start + Ei - 1]++;`'
en4 English Ashwanth.K 2024-09-24 12:18:05 402 (published)
en3 English Ashwanth.K 2024-09-24 12:14:07 143
en2 English Ashwanth.K 2024-09-24 12:07:18 2990
en1 English Ashwanth.K 2024-09-24 11:43:54 696 Initial revision (saved to drafts)