RECIPEE - Editorial

PROBLEM LINK:

Pizza Recipe
Practice
Author: naveen19991124
Editorialist: naveen19991124
Tester: hellb0y_suru

PROBLEM:

Given an array of N integers, divide the given array into non-overlapping contiguous groups of size at least K in such a way that the maximum of the costs of groups is minimized, where the cost of any group is defined as the difference between the maximum and minimum values present in the group.

PREREQUISITES:

  • Binary Search
  • Dynamic Programming

DIFFICULTY:

EASY-MEDIUM

EXPLANATION:

The optimal partition of the array into groups of size at least K can be done for a sorted array. If for a given cost c, we can partition our array into some non-overlapping non-contiguous groups of at least size K, then we can definitely do the same for some cost cā€™ > c - Binary Search!.

So, we can binary search on the answer which is basically the overall cost say c. We can maintain an array valid[i], which is true if it is possible to partition the array till index i, according to the given condition, so if we are at index i, then we need to check whether a valid partition can be made or not on including arr[i].

How to check ?

The partition must start at index last(minimum index), such that last < i and arr[last] - arr[i] <= c, now we iterate index j from last to i, until we get valid[j - 1] = true (as we consider a partition to be from j to i), which means there exists a valid partition at index (j - 1), and since last<=j<i, the difference between arr[i] and arr[j] <= c, now we just need to check if (i-j+1)<=k, then we have a valid partition at index i. Finally if valid[n] = true, then we can partition our array for given cost c.

Everything mentioned above can be maintained by a single pointer, refer to the code for better understanding.

Time complexity: O(N.logK), where K is at most 1e9.

Alternative Approach

We can binary search over our answer, say c and to determine whether there exists a valid partition at index i, we simply can maintain a valid array, where valid[j] = true denotes that there exists a valid partition at index j, now we need to determine if there exists a valid partition from index last(minimum index) to i-k+1, such that last < i and arr[last] - arr[i] <= c, last can be easily found using binary search on prefix sum array. We can simply maintain a BIT tree/Segment tree over valid array and perform a range query from index last to i-k+1 to check if there exsists any non-zero value in this range, and accordingly update our BIT tree/Segment tree at current index i.Finally if valid[n] = true, then we can partition our array for given cost c.

Time complexity: O(N.logN.logK), where K is at most 1e9.

SOLUTION:

Setter's Solution in C++
//AUTHOR - NAVEEN KUMAR
//2021-03-17
//02:31:32

//The Game Is ON!!!
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_update
//#include<boost/multiprecision/cpp_int.hpp>
//#inlcude<boost/multiprecision/cpp_dec_float.hpp>
#define ll long long
#define ld long double
#define F first
#define S second
#define nl "\n"
#define mem(v, t) memset(v, t, sizeof(v))
#define all(v) v.begin(), v.end()
#define sz(v) (ll)(v.size())
#define srt(v) sort(all(v))
#define rsrt(v) sort(v.rbegin(), v.rend())
#define pb push_back
#define f(a) for (ll i = 0; i < a; i++)
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, a, b) for (ll i = a; i > b; i--)
#define vll vector<ll>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define mp make_pair
#define hell 1000000007
#define PI 3.141592653589793238462643383279502884197169399375
#define INF (ll)(1e18 + 5)
#define fast                        \
 ios_base::sync_with_stdio(false); \
 cin.tie(NULL);                    \
 cout.tie(NULL);

using namespace std;
using namespace std::chrono;
using namespace __gnu_pbds;

ll arr[200000];
ll n, k;

bool can(ll mid)
{
 ll cur = 1;
 ll valid[n + 1];
 for (ll i = 0; i <= n; i++)
 {
   valid[i] = 0;
 }

 valid[0] = 1;
 if (arr[k] - arr[1] <= mid)
   valid[k] = 1;

 for (ll i = k + 1; i <= n; i++)
 {
   while (arr[i] - arr[cur] > mid)
   {
     cur++;
   }
   while (!valid[cur - 1] and cur < i)
   {
     cur++;
   }

   if (cur <= i - k + 1)
     valid[i] = 1;
 }
 return valid[n];
}

//MAIN CODE
int main()
{
 fast
 ll t;
 cin >> t;
 while (t--)
 {
   cin >> n >> k;
   rep(i, 1, n + 1)
   {
     cin >> arr[i];
   }

   sort(arr + 1, arr + n + 1);

   ll lo = 0;
   ll hi = INF;

   ll ans = INF;
   while (lo <= hi)
   {
     ll mid = lo + (hi - lo) / 2;
     if (can(mid))
     {
       ans = mid;
       hi = mid - 1;
     }
     else
     {
       lo = mid + 1;
     }
   }
   cout << ans << "\n";
 }
 return 0;
}

//The Game Is OVER!!!
Tester's Solution in C++
#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007 
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)

using namespace std;

class SegTreeMM{
   private:
       vector< pair<long long,long long> > v;
       int n;
       pair<long long,long long> merge(const pair<long long,long long> &a,const pair<long long,long long> &b){
           return make_pair(min(a.first,b.first),max(a.second,b.second));
       }
       void update(int id,int pos,long long val,int s,int e){
           if(s>e) return;
           else if(s==e){
               v[id].first = val;
               v[id].second = val;
               return; 
           }
           int mid = (s+e)/2;
           if(pos<=mid) update(2*id,pos,val,s,mid);
           else update(2*id+1,pos,val,mid+1,e);
           v[id] = merge(v[2*id],v[2*id+1]);
           return;
       }
       pair<long long,long long> query(int id,int l,int r,int s,int e){
           if(s>e || e<l || r<s) return make_pair(oo,-oo);
           if(l<=s && e<=r) return v[id];
           pair<long long,long long> a = query(2*id,l,r,s,(s+e)/2);
           pair<long long,long long> b = query(2*id+1,l,r,(s+e)/2+1,e);
           return merge(a,b);
       }
   public:
       SegTreeMM(vector<long long> &a){
           n = a.size();
           v.assign(4*n+10,make_pair(oo,-oo));
           for(int i=1;i<=n;i++){
               update(i,a[i-1]);
           }
       }
       SegTreeMM(int n){
           this->n = n;
           v.assign(4*n+10,make_pair(oo,-oo));
       }
       void update(int i,long long val){
           update(1,i,val,1,n);
       }
       pair<long long,long long> query(int l,int r){
           return query(1,l,r,1,n);
       }

};

int getId(ll a[],int n,int i,ll x){
   int l = 1 , r = i;
   int ans = 1;
   while(l<=r){
       int mid = (l+r)>>1;
       if(a[i]-a[mid]<=x){
           ans = mid;
           r = mid-1;
       }
       else l = mid+1;
   }
   return ans;
}

void __sol(){
   int n,m; cin >> n >> m;
   ll a[n+1];
   a[0] = 0;
   forr(i,n) cin >> a[i+1];
   if(m == 1){
       cout << 0 <<"\n";
       return;
   }
   sort(a+1,a+n+1);
   ll dp[n+2];
   forr(i,n+2) dp[i] = oo;
   SegTreeMM s(n+2);
   dp[0] = 0;
   dp[m] = a[m] - a[1];
   s.update(m+1,dp[m]);
   for(int i=m+1;i<=n;i++){
       ll l = a[i] - a[i-m+1] , r = a[i]-a[1];
       while(l<=r){
           ll mid = (l+r)>>1;
           int id = getId(a,n,i,mid);
           ll cnt = s.query(id,i-m+1).FF;
           if( cnt <= mid ){
               dp[i] = mid ;
               r = mid-1;
           }
           else l = mid+1;
       }
       dp[i]=min(dp[i],a[i]-a[1]);
       s.update(i+1,dp[i]);
   }
   cout << dp[n]<<"\n";
   return;
}


int main(){  
   fastio;
   ll tc=1;  cin >> tc;
   while(tc--) __sol();
   return 0;
}

Let me know if there are other solutions to the problem as well :smiley:

1 Like