CKBKFR - EDITORIAL

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Pranjul Pal
Tester: Sonali Singh
Editorialist: Pranjul Pal

DIFFICULTY:

EASY

PREREQUISITES:

Binary Search

PROBLEM:

Given N different book numbered from 1 to N, if someone buys K books with indices x_1, x_2, \dots, x_K then cost of book x_j is (Axj + xj * K) for (1 \le j \le K) . Find maximum number of books possible to buy without paying more than R rupees and total cost paid. If there are many ways to maximize number of books then then find the answer with minimum total cost paid.

QUICK EXPLANATION:

Use binary search to find the best value of K.
For each K, find new price of all the books and select the K minimum prices.

EXPLANATION:

We have to maximize the number of books bought.
Observation 1: If Pragati buys K books optimally (i.e. K books at minimum possible price), then she can also buy less than K books since it will be still in her budget.

Observation 2: If she can’t buy K books optimally, then she also can’t buy more than K books, it will obviously exceed her budget.

Thus, to find the best value of K and in order to reduce the time complexity we can use binary search here.

Applying binary search:
In a search range, if K is mid-value of search range, then for K calculate the new prices of books (according to: (Axj + xj * K) ), sort them and pick K minimum prices.
Then, according to above two observations, if this cost is under budget, search in the right half of search range else find answer in left half of search range.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vll vector<ll>
#define vpll vector<pll>
#define vvll vector<vector<ll>>
#define sll stack<ll>
#define qll queue<ll>
#define mp make_pair
#define f first
#define s second
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define init(x,n,v) for(ll i=0;i<=n;i++) x[i]=v;
#define all(x) x.begin(),x.end()
ll MOD = 1e9+7 , MAX = 1e18;
int main() 
{
	fast_io;
	Test
	{
    	ll n,k,i,l,r,m,ans1,ans2;
    	cin>>n>>k;
    	vll a(n+1);
    	for(i=1;i<=n;i++) cin>>a[i];
    	l=0 , r=n;
    	while(l<=r)
    	{
    	    m=(l+r)/2;
    	    vll a1=a;
            ll sum=0;
            for(i=0;i<=n;i++) a1[i]+=(i*m);
            sort(all(a1));
            for(i=0;i<=m;i++) sum+=a1[i];
            if(sum<=k) l=m+1 , ans2=sum , ans1=m;
    	    else r=m-1;
    	}
    	cout<<ans1<<" "<<ans2<<ln;
	}
	return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,S;
        cin>>n>>S;
        ll a[n],b[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        ll l=0,r=n,k,ans;
        while(l<=r){
            ll m=(l+r)/2;
            ll sum=0;
            for(int i=0;i<n;i++)
                b[i]=a[i]+((i+1)*m);
            sort(b,b+n);
            for(int i=0;i<m;i++)
                sum+=b[i];
            if(sum>S)
                r=m-1;
            else{
                l=m+1; 
                k=m;
                ans=sum;
            }
        }
        cout <<k<<" "<<ans<< endl;
    }
    return 0;
}
3 Likes