CCC-Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

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 :

  1. Select a coconut at random among the previously not selected ones, and hit it A[i] times.
  2. 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

  1. Pick a label A[i], \hspace{0.2cm} i < last

  2. 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.

  3. 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.

  4. 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;
}
11 Likes

wonderful question :smile:

3 Likes

Weak Test cases some N^2*Z solutions with constant optimizations got AC.

5 Likes

There is a somewhat less complicated solution without the convex hull.
https://www.codechef.com/viewsolution/25276044

It simply optimizes the inner loop, so complexity is more than O(n^2), but still much less than O(n^3)

2 Likes

Great Problem. Although couldn’t solve it. But it kept me busy thinking for the solution.

nice editorial too…

5 Likes

Under the Full Score heading, there is a sentence “Initially let last = n + 1.” What is “n”? Is it the same as “N”, or something different?

Oh, its N ( And some unnecessary words to make 20 chars)

1 Like

I don’t think it will cost O (Tnzlnz) because I only spent O (Tnz) using the stack.
My solution:https://www.codechef.com/viewsolution/25098609

6 Likes

You should make unofficial editorials :laughing: …You seem to know a little too much

3 Likes

I’m not suitable for very detailed editorials, because my English is not good.

5 Likes

Yes ofcourse your implementation of cht is without bs, mine uses bs, hence the extra log(N) factor

Can anyone provide me some tough test cases for the problem as I am not getting where my code is going wrong. thanks in advance:)

2 Likes

Take a working code and…instead of reading inputs just randomize them and print the input and solution…u will get a case which your code gives wrong answer for.

Shouldn’t this be O(N)

Could you describe your solution in brief? @anand20 mentioned you’re using convex hull trick without binary search. Could you shed some light on that. Thanks!

Maybe it’s a dumb question, but I couldn’t understand why this problem cannot be solved with Divide and Conquer Optimization.
Someone? :grimacing:

Is your scan function faster than fastIO generally used by c++ programmers?

No, we have to sort the given array right ?

1 Like

Many solutions have passed with simple greedy approaches and most of them don’t seem to have used cht… Maybe this editorial could be much more easy in term of advanced concepts? Nice editorial btw :slight_smile:

I believe it can be solved using divide and conquer optimization

1 Like