12 months ago

Amit kumar • 20

Dhanbad

1) Binary search, but for checking whether mid is valid, we can use dynamic programming with bitmasking (because we have to use at max two shops so In the current mask we stored all the stones that we have already taken) to find the minimum cost required to size all stones equal to mid .

int f(int i,int count,int mask,vector<vector<int>>&v,int mid){
    if(count==2)return 0;
    if(i==v.size())return 1e18;
    int &ans=dp[i][count][mask];
    if(ans!=-1)return ans;
    ans=f(i+1,count,mask,v,mid);
    if(count==0){
    int n=v[0].size();
    for(int curr_mask=0;curr_mask<(1<<n);++curr_mask)
    {
    int sum=0;
    for(int j=0;j<n;++j)
    if(curr_mask&(1<<j))
    sum+=(mid+v[i][j]-1)/v[i][j];
    ans=min(ans,f(i+1,1,curr_mask,v,mid)+sum);
    }
    }
    else if(count==1){
    int n=v[0].size();
    int sum=0;
    for(int j=0;j<n;++j)
    if((mask&(1<<j))==0)
    sum+=(mid+v[i][j]-1)/v[i][j];
    ans=min(ans,f(i+1,2,(1<<n)-1,v,mid)+sum);    
    }
    return ans;    
}

// in main function use binary search

int n,k;cin>>n>>k;
vvi v(n,vi(k));
rep(0,i,n)rep(0,j,k)cin>>v[i][j];
int s;cin>>s;
int l=0,h=1e13,mid,ans=l;
while(l<=h){
    mid=(l+h)/2;
    dp.clear(),dp.resize(n,vector<vector<int>>(3,vector<int>(1<<k,-1)));
    if(f(0,0,0,v,mid)<=s)ans=mid,l=mid+1;
    else h=mid-1;
}
cout<<ans<<"\n";

2) can be done by segment tree with lazy propagation . One can try a similar problem :

https://leetcode.com/problems/handling-sum-queries-after-update

3)can be done using matrix exponentiation