#### Problem D2: Line of Delivery (Part 2) [Link](https://www.facebook.com/codingcompetitions/hacker-cup/2024/practice-round/problems/D2) ↵
↵
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: ↵
↵
↵
↵
Herepc30GR.png)↵
↵
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 this case, the `emptyPlaces` array looks likee 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,12,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. ↵
↵
↵
<spoiler summary="Code">↵
↵
```↵
// #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++;↵
for(int guys = 0 ; guys < emptyPlaces[x] ; guys++)↵
{↵
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;↵
}↵
```↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
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: ↵
↵
↵
↵
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 th
↵
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. ↵
↵
↵
<spoiler summary="Code">↵
↵
```↵
// #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++;↵
for(int guys = 0 ; guys < emptyPlaces[x] ; guys++)↵
{↵
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;↵
}↵
```↵
↵
↵
↵
</spoiler>↵
↵
↵
