PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iiii63027
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
N elves are present on a line, the i-th at position X_i.
Assign these elves to toys such that:
- At least two elves are assigned to each toy.
- All elves assigned to the same toy will meet at a single point to work on it.
They will choose the point that minimizes the maximum walking distance. - Across all assignments, minimize the maximum distance travelled by any elf.
- Across all assignments satisfying the above, the number of toys should also be minimized.
EXPLANATION:
First, we’ll compute the minimum possible maximum distance travelled.
One thing to note about this distance is that for a fixed group of elves, it only depends on the leftmost and rightmost among them.
More precisely, if elves at Y_1, Y_2, \ldots, Y_k are assigned to the same group, they will meet at exactly the point \frac{(Y_1 + Y_k)}{2}, i.e, the midpoint of the segment [Y_1, Y_k]$.
In particular, this tells us that it’s optimal to partition elves into contiguous segments based on their positions.
Let’s use that fact to compute the minimum possible maximum distance.
While there are a few different ways to do it, here’s one way to compute the required value in \mathcal{O}(N).
Let dp_i denote the minimum possible maximum distance if we’ve only considered the first i elves.
dp_0 = 0, and dp_1 = \infty (since it isn’t allowed for a single elf to work on a toy).
Now, for i \geq 2, the natural transition is as follows:
- Fix j \lt i as the left endpoint of the segment we’re considering.
Then, the obtained maximum length is \max(dp_{j-1}, (X_i - X_j)/2), since the last segment is fixed and then the first j-1 elves are partitioned optimally. - Try this for all j \lt i and take the minimum among them.
This is \mathcal{O}(N^2), of course.
However, here’s where we notice something nice: it’s enough to consider only segments of small length - in fact, considering only length 2 and 3 is enough!
Why?
Suppose the optimal solution contains a segment of length \geq 4.
We can “cut off” the last two elves from this segment to form a new segment with them alone, which won’t increase the maximum distance traveled.
Repeat this till every segment has length \leq 3, and we have a solution that isn’t worse than optimal.
So, instead of trying every j \lt i, it’s enough to check for j = i-1 and j = i-2.
This immediately brings the time complexity down to \mathcal{O}(N).
We now know the minimum possible maximum distance: dp_N.
Let this be L, for convenience of notation.
Our next task is to find the minimum number of segments that the elves can be partitioned into, such that each segment used has length \leq 2L.
There are, once again, several ways to do this - one of them is below.
First, for each i, let R_i denote the farthest right endpoint such that the segment [i, R_i] is still good.
That is, R_i is the largest integer such that X_{R_i} - X_i \leq 2L.
Finding all the values of R_i can be done fairly easily with binary search or two pointers.
Now, let’s use dynamic programming once again.
Let m_i denote the minimum number of segments of length \leq 2L needed to cover the elves from i to N.
We have m_{N+1} = 0 and m_N = \infty, as before.
Then, for each i from N-1 down to 1, we have a similar transition as we did in the first step: for each i \lt j \leq R_i, set m_i \gets \min(m_i, 1 + m_{j+1}) by trying to use the segment [i, j].
While this is quadratic, once again a similar trick works to optimize it: it’s enough to only care about j = R_i and j = R_i-1.
Why?
Let j_0 be the optimal right endpoint for index i, that gives us m_i.
Suppose j_0 \lt R_i - 1.
Consider the segment immediately after j_0, i.e, that starts at j_0 + 1.
If this segment ends \leq R_i, we could’ve just included it in the segment starting at i itself and saved one segment; so this cannot be optimal.
That means it ends \gt R_i; and in particular, contains both indices R_i and R_{i}+1.
So, we can instead choose the segment [i, R_i-1] and shrink the following segment to start at R_i - the number of segments stays the same, and they’re all still \leq 2L in length.
This improves the complexity to \mathcal{O}(N).
The final answer is m_1.
As a final note, even though the distance is a floating-point value, you can notice that it’s always either an integer or half an integer (because of how the meeting point is computed).
That is, it’s always either x.0 or x.5 for an integer x.
This allows you to skip out working with floating-point values entirely and always print the exact answer, if you’d like to do so.
\mathcal{O}(N\log N) solutions with reasonably low constants will also likely pass.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
class Solution{
public:
int n;
set<int>availables;
int ans=false;
int toys(int index,vector<int>&x,double mid){
if(availables.find(index)==availables.end())return 0;
availables.erase(index);
if(index+1==n)return 0;
if(x[index+1]-x[index]>2*mid)return 0;
if(x.back()-x[index]<=2*mid)return 1;
if(availables.size()==0)return 0;
int ok=false;
int i=upper_bound(x.begin(),x.end(),x[index]+2*mid)-x.begin();
auto it=availables.lower_bound(i);
if(it==availables.end())it--;
while(availables.size()){
if(it==availables.begin())break;
if(*it<=index+1)return 0;
if(x[*it-1]-x[index]>2*mid){
it--;
continue;
}
int itr=*it;
ok=toys(itr,x,mid);
if(ok)return 1+ok;
it=availables.lower_bound(i);
if(it==availables.begin())break;
if(it==availables.end())it--;
}
return 0;
}
vector<double>dp1;
double find(int i,vector<int>&a,int many){
double sum=a[i]+a[i+many-1];
sum/=2;
return max(abs(a[i]-sum),abs(a[i+many-1]-sum));
}
double findDistance(int index,vector<int>&a,int n){
if(index==n)return INT_MIN;
if(index==n-1||index>n)return INT_MAX;
if(dp1[index]!=-1)return dp1[index];
dp1[index]=max(find(index,a,2),findDistance(index+2,a,n));
dp1[index]=min(dp1[index],max(find(index,a,3),findDistance(index+3,a,n)));
return dp1[index];
}
double getMinimum(vector<int>&x){
n=x.size();sort(x.begin(),x.end());
dp1.assign(n+1,-1);
double trueValue=findDistance(0,x,n);
for(int i=0;i<n;i++)availables.insert(i);
cout<<setprecision(10)<<trueValue<<' ';
return toys(0,x,trueValue);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin>>t;
assert(t<=100000&&"T <= 1e5");
int sum=0;
while(t--){
int n;cin>>n;
sum+=n;
assert(n<=1000000&&"N <= 1e6");
assert(n>=2&&"N>=2");
vector<int>x(n);
for(int &it:x)cin>>it;
assert(is_sorted(x.begin(),x.end())&&"X must be sorted");
assert(x[0]>=1&&x.back()<=1e9&&"X values between 1 and 1e9");
cout<<Solution().getMinimum(x)<<endl;
}
assert(sum<=1000000&&"SUM(N <= 1e5");
}
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll int
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 1e6 + 4;
const ll mod = 1e7 + 7;
// const ll mod = 998244353;
vl mp;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
ll aloo(pair<ll,ll> p){
return (p.second-p.first)*mod+p.first;
}
ll barfi(ll v, vl &a, ll l, ll r){
if(l==r){
mp[v]=a[l];
}
else{
ll m=(l+r)/2;
mp[v]=min(barfi(2*v,a,l,m),barfi(2*v+1,a,m+1,r));
}
return mp[v];
}
ll kulfi(ll v, ll l, ll r, ll l1, ll r1){
if(l1>r) return mod;
if(r1<l) return mod;
if(l1>=l && r1<=r) return mp[v];
ll m=(l1+r1)/2;
return min(kulfi(2*v,l,r,l1,m),kulfi(2*v+1,l,r,m+1,r1));
}
ll papdi(ll v, vl &a, ll l, ll r, ll x){
if(x<l || x>r) return mp[v];
if(l==r){
mp[v]=a[l];
}
else{
ll m=(l+r)/2;
mp[v]=min(papdi(2*v,a,l,m,x),papdi(2*v+1,a,m+1,r,x));
}
return mp[v];
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s;
bool ch = true;
cin >> n;
vl a(n);
forl(i, 0, n) {
cin >> a[i];
a[i]*=2;
}
ll l=0,r=2e9;
r+=5;
while(l+1<r){
m=(l+r)/2;
vl dp(n+1);
dp[0]=1;
c=0;
ll c1=-1;
forl(i,0,n){
k=lower_bound(all(a),a[i]-2*m)-a.begin();
if(k<i && (c1>=k || (c>=k && c<i))) {
dp[i+1]=1;
c1=c;
c=i+1;
}
}
// cout<<dp[1]<<' ';
if(dp[n]) {
r=m;
}
else l=m;
}
mp.clear();
mp.resize(4*n);
vl dp1(n+1,mod);
dp1[0]=0;
barfi(1,dp1,0,n);
forl(i,0,n){
k=lower_bound(all(a),a[i]-2*r)-a.begin();
if(k<i) {
c=kulfi(1,k,i-1,0,n);
if(c<mod){
dp1[i+1]=c+1;
papdi(1,dp1,0,n,i+1);
}
}
}
cout<<fixed;
cout<<setprecision(10);
cout<<(r*0.5)<<' '<<dp1[n];
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
x = [0] + list(map(int, input().split()))
dp = [0]*(n+1)
dp[0] = 0
dp[1] = 10**18
for i in range(2, n+1):
dp[i] = max(dp[i-2], x[i] - x[i-1])
if i >= 2: dp[i] = min(dp[i], max(dp[i-3], x[i] - x[i-2]))
mxlen = dp[n]
R = [0]*(n+1)
ptr = 1
for i in range(1, n+1):
while ptr < n:
if x[ptr+1] - x[i] <= mxlen: ptr += 1
else: break
R[i] = ptr
dp = [10**18]*(n+2)
dp[n+1] = 0
for i in reversed(range(1, n)):
dp[i] = 1 + dp[R[i]+1]
if R[i] > i+1: dp[i] = min(dp[i], 1 + dp[R[i]])
print(mxlen/2, dp[1])