PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Setter : Abhinav Jain
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
Medium
PREREQUISITES :
Dynamic Programming, Basic Geometry, Convex Hull Trick
PROBLEM :
You are given N labels A_1,A_2...A_N, and there exist N coconuts associated with them. For each i, there exists a coconut that requires exactly A_i hits to break open. You don’t know which coconut requires how many hits to open.
You need to find the minimal number of hits required to break open Z coconuts in the worst case.
EXPLANATION :
Let’s sort the given input array A in non-decreasing order, that’s gong to help us throughout the task. Also, let’s call the number of hits a coconut requires to open as its power.
Sub task 1
Assume we are trying to open a coconut with power exactly A[i] among the given ones. Then, we could use one of the following 2 strategies :
- Select a coconut at random among the previously not selected ones, and hit it A[i] times.
- Select a coconut, we didn’t hit in the previous N rounds, and hit it some number of times < A[i] .
Using the first strategy, it the worst case, we will make a maximum number of ( N-i+1 ) \cdot A[i] hits. However, using the second strategy we will always make greater number of hits in the worst case.
For example, assume the given input array is : [2,2,5,9], and we are trying to open a coconut with power 2. Then, using the first strategy, the following happens in the worst case :
We hit one coconut randomly 2 times. It doesn’t open. We hit another coconut 2 times, it doesn’t open. Now, if we hit any other coconut 2 times, it has to open. So, the number of hits used is 6.
Using the second strategy, the following happens :
We hit some coconut once. Then another one, then another one, and so on. This will take 7 hits in the worst case.
So, what we can do is, fix the power of the coconut we are looking for. Then, using the first strategy, find the minimum number of hits to open such a coconut.
The answer then obviously is : min_{i=1}^{N} A[i] \cdot (N-i+1)
The time required to solve this subtask is O(N \cdot \log(N))
Full Score
In case Z>1, we can clearly understand from the constraints, the expected solution is somewhere along the lines of O ( N \cdot Z ) . First, we propose the following optimal algorithm :
Initially let last=n +1 . Sort the given array in non-decreasing order
-
Pick a label A[i], \hspace{0.2cm} i < last
-
Now, we keep choosing coconuts with power > A[i] in the worst case, until we finally get the coconut with power = A[i] . We hit all of them X times, using a total number of (last-i) \cdot A[i] hits here.
-
Now, we have identified all coconuts with power > A[i] and we shall never hit them again. Assume, we dispose all such coconuts into a bin. If they were optimal to hit, we should have used the label associated with it’s power to open it before.
-
Now, set last=i and go to step 1
If we perform this algorithm exactly Z times, selecting the A[i] optimally, then that is the answer we are looking for.
Proof of Optimality of Algorithm
First of all, it’s never ever optimal to hit coconuts a single time 1 by 1. Assume we’re trying to open a coconut with power X. Then, by doing so, we also hit coconuts with power < X and power > X and also coconuts with power =X.
In the worst case, this could lead to far greater hits that just choosing coconuts and hitting them X times.
An other question that arises is in cases like :
4 4
2 3 5 10
One may ask we can skip label 10, and then beat 2 coconuts 5 times, 2 coconuts 3 times and 2 coconuts 2 times, and we have all 4 coconuts open. How to handle this ?
The answer to this is : It was already optimal to select label 10 and beat 1 coconut 10 times, then beat 1 coconut 5 times, 1 coconut 3 times and 1 coconut 2 times, both of them lead to the same number of hits.
So, if a coconut with power X is among the Z open coconuts, then it’s always going to be optimal to use the label associated with it. There cannot be a scenario when we have a coconut with power X open, using lesser hits without using the label it’s associated with , than with using it’s label.
So, the Z coconuts we want open will be the associated exactly to the Z labels we use.
Here, We propose a dynamic programming solution based on the algorithm above.
Let dp[i][j] indicate the minimum cost to successfully open j coconuts with powers from the suffix i,i+1..n, with the i^{th} power being the last used one.
Obviously dp[i][1]=a[i] \cdot (n-i+1) \hspace{0.2cm} \forall i
Then, if we want to calculate dp[i][j] for some j \ge 2 we can do it as follows :
dp[i][j] = min_{k=i+1}^{n} dp[k][j-1] + (k-i) \cdot a[i] .
This dynamic programming exactly simulates the algorithm above considering each possible Z sized subset along the way.
To calculate this recurrence naively would take an overall run time of O( N^2 \cdot Z). This does not give us a single additional point unfortunately. Here, we can notice the special form of the recurrence, we can rewrite it as :
dp[i][j] = min_{k=i+1}^{n} dp[k][j-1] + k \cdot a[i] - i \cdot a[i] .
The i \cdot a[i] term is just a constant we need to add. Then part that then needs to be minimized is the dp[k][j-1] + k \cdot a[i] . You can notice that this recurrence very closely resembles the equation of a line in the form y= m \cdot x + b . We assume m=k and b=dp[k][j-1]
The following sub-task needs to be solved now : We have many possible (m,b) pairs ( lines) , and we need to try and minimize the y co-ordinate for a fixed x.
Now, since the k always appear in decreasing order, there exists a very popular way for solving such a problem called the Convex Hull Trick. You can read about it here.
We can resolve each such query in O(log(N)) time, that leads to an overall runtime of O( N \cdot Z \ log(N))
Finally, we looking for the minimum among dp[i][z] \hspace{0.2cm} \forall i and print it.
COMPLEXITY ANALYSIS :
Time Complexity : O( T \cdot ( N \cdot Z \cdot ln(N) ) )
Space Complexity : O ( N \cdot Z )
SOLUTION LINKS :
Setter
// Author : Abhinav Jain
// Institution: Jaypee Institute of information Technology
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define lli long long int
#define pb push_back
#define mp make_pair
#define cases lli testcases;cin>>testcases; while(testcases--)
#define trace(x) cerr << '>' << #x << ':' << x << endl;
#define trace2(x,y) cerr<< '>' << #x << ':' << x << " | " << #y << ':' << y << endl;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<vi> vii;
typedef vector<pii> vpii;
typedef map<int,int> mii;
int MOD= 1000000007LL;
template<typename T>
T mult(T x,T y,T mod){
return(((x%mod)*(y%mod))%mod);
}
template<typename T>
T add(T x,T y,T mod){
return(((x%mod)+(y%mod))%mod);
}
template<typename T>
T gcd(T x,T y){
return(!y?x:gcd(y,x%y));
}
template<typename T>
T lcm(T x,T y){
return((x*y)/gcd(x,y));
}
int32_t main()
{
cases
{
lli N,Z;
cin>>N>>Z;
lli res =0;
lli A[100005];
for(lli i=0;i<N;i++){
cin>>A[i];
}
if(N==Z){
for(lli j=0;j<N;j++){
res+=A[j];
}
}
else{
sort(A, A+N);
res=INT_MAX;
lli add2=0;
for(lli i=0;i<Z;i++){
lli add3=0;
for(lli n=0;n<Z-i;n++){
add3+=A[N-n-1];
}
lli CNT = N-Z+1;
for(lli j=N;0<=j-Z;j--)
{
CNT--;
lli mult=(i==0)?0:A[i-1];
lli ans=add2+add3+A[j-1]*(N-j)+mult*CNT;
res=min(res,ans);//if(ans<res)res=ans;
if(0<=j-(Z-i)-1)
add3=add3+A[j-(Z-i)-1]-A[j-1];
}
add2+=A[i];
}
}
cout<<res<<endl;
}
return 0;
}
Tester
# include<bits/stdc++.h>
using namespace std;
const int N = 5000 + 77;
const long long inf = 2e18;
int T;
int n , z , a[N];
long long ans , ps[N];
inline void Test() {
ans = inf;
scanf("%d %d" , & n , & z);
for(int i = 1;i <= n;++ i)
scanf("%d" , a + i);
sort(a + 1 , a + 1 + n);
for(int i = 1;i <= n;++ i)
ps[i] = ps[i - 1] + a[i];
for(int k = 0;k <= z;++ k) {
int f = z - k;
long long tot = ps[n] - ps[n - k];
for(int i = f;i <= n - k;++ i)
ans = min(ans , tot + ps[i] - ps[i - f] + max(0 , (n - k - i)) * 1ll * a[i]);
}
for(int k = 0;k <= z;++ k) {
int f = z - k;
int t = a[k];
long long tot = ps[k] + (n - k) * 1ll * t;
for(int i = k + 1;i + f - 1 <= n;++ i) {
int le = i , ri = i + f - 1;
ans = min(ans , (n - ri) * 1ll * (a[ri] - t) + tot + ps[ri] - ps[le - 1] - f * 1ll * t);
}
}
printf("%lld\n" , ans);
}
int main() {
scanf("%d" , & T);
while(T --)
Test();
return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(1e3+3);
const ll mod=(ll)(1e9+7);
int a[maxn];
ll dp[maxn][maxn];
vector< pll > cv_hull[maxn];
ll eval(pll y,ll x)
{
return y.first*x+y.second;
}
bool isBad(int idx,int i,int j,int k)
{
ll val1=cv_hull[idx][i].second-cv_hull[idx][k].second,val2=cv_hull[idx][k].first-cv_hull[idx][i].first;
ll val3=cv_hull[idx][i].second-cv_hull[idx][j].second,val4=cv_hull[idx][j].first-cv_hull[idx][i].first;
return (val1*(1.0)*val4)<=(val2*1.0*val3);
}
void insert(int idx,pll x)
{
cv_hull[idx].pb(x);
while(cv_hull[idx].size()>=3 && isBad(idx,cv_hull[idx].size()-3,cv_hull[idx].size()-2,cv_hull[idx].size()-1))
{
cv_hull[idx].erase(cv_hull[idx].begin()+cv_hull[idx].size()-2);
}
}
ll query(int idx,ll x)
{
int low=0,high=cv_hull[idx].size()-1;
while(high-low>2)
{
int mid=(low+high)>>1;
ll val1=eval(cv_hull[idx][mid],x),val2=eval(cv_hull[idx][mid+1],x);
if(val2<val1)
{
low=mid;
}
else
{
high=mid;
}
}
ll ret=LONG_LONG_MAX;
for(int i=low;i<=high;i++)
{
ret=min(ret,eval(cv_hull[idx][i],x));
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
while(t>0)
{
int n,z;cin>>n>>z;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
for(int j=1;j<=z;j++)
{
dp[i][j]=LONG_LONG_MAX;
}
}
for(int j=1;j<=z;j++)
{
cv_hull[j].clear();
}
for(int i=n-1;i>=0;i--)
{
dp[i][1]=a[i]*(n-i);
for(int j=2;j<=z;j++)
{
dp[i][j]=query(j-1,a[i])-(i*a[i]);
}
for(int j=1;j<=z;j++)
{
insert(j,{i,dp[i][j]});
}
}
ll res=LONG_LONG_MAX;
for(int i=0;i<n;i++)
{
res=min(res,dp[i][z]);
}
cout<<res<<endl;t--;
}
return 0;
}
…You seem to know a little too much
