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. So emptyPlaces[i] denoted how many consecutive balls are immediately right towards $$$i^{th}$$$ empty slot. 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) emptyPlaces[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 $$$[0,1,2,1,0,0]$$$

Let's say a ball is thrown with $$$E = 4$$$, then the $$$4^{th}$$$ empty position is occupied by this new red ball.

Now Since this new ball has collided with the previous 3 balls at position 3,5,6 then these balls move 1 unit towards left.

This can be visualized like adding a new empty slot on left of new ball, and deleting an empty slot at the start of the track.

Now if we notice the emptyPlaces array, it changes to $$$[1,2,2,0,0]$$$. After adding the empty slot and new ball combined to $$$4^{th}$$$ position, the emptyPlaces array changes to $$$[0,1,2,2,0,0]$$$. Since the previuos balls move 1 unit left, we can delete the first element in emptyPlaces array and it changes to $$$[1,2,2,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.

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
		
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<pair<ll , ll>> vpll;
typedef vector<pair<ld , ld>> vplld;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef priority_queue<ll> pq;
typedef priority_queue<pair<ll,ll>> pqp;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define print(a) for(auto x:a) cout<<x<<" ";cout<<endl;
#define printarr(a , n) for(int i = 0 ; i < n  ;i ++) cout << a[i] << " "; cout << endl;
#define endl '\n'
#define sq(a) (a)*(a)
#define yes  cout << "YES" << endl;
#define no  cout << "NO" << endl;


int emptyPlaces[2000005] = {0};

void solve()
{
	ll n , k;
	cin >> n >> k;

	vl a(n);
	for(int i =  0 ; i < n ; i ++)
	{
		cin >> a[i];
	}

	// clear all empty information
	for(int i = 0 ; i < 2000005 ; i ++)
	{
		emptyPlaces[i] = 0;
	}

	int start = 0;

	for(int i = 0 ;i  < n ; i ++)
	{
		emptyPlaces[start + a[i] - 1]++;
		start++;
	}

	int position = 1;
	vl ballPosition;

	for(int x = start ; x < 2000005 ; x ++)
	{
		position++;  // currently I have a empty slot
		for(int guys = 0 ; guys < emptyPlaces[x] ; guys++)
		{
                        // balls occupied to the right of this empty slot
			ballPosition.pb(position++);
		}
	}	

	reverse(ballPosition.begin() , ballPosition.end());

	pll ans = {inf , inf};

	for(int i = 0 ;i  < n ; i ++)
	{
		ans = min(ans , {abs(ballPosition[i]-k) , i+1});
	}
	cout << ans.second << " " << ans.first << endl;
}

int main(){

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	

	#ifndef ONLINE_JUDGE
		freopen("line_of_delivery_part_2_input.txt", "r" , stdin);
		freopen("output.txt", "w" , stdout);
	#endif

	int t=1;
	cin>>t;

	for(int i = 1 ; i <= t ; i ++)
	{
		cout <<"Case #"<<i<<": ";
    	solve();
	}	
	return 0;
}