BUYSWEET Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Yash Thakker
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra

DIFFICULTY:

1706

PREREQUISITES:

None

PROBLEM:

There are N sweets in the store. The cost of the i^{th} sweet is A_i rupees. Chef is a regular customer, so after buying the i^{th} sweet, he gets a cashback of B_i rupees.

Chef has R rupees. He is fond of all the sweets, so he wants you to calculate the maximum number of sweets he can buy. Note that he can buy the same type of sweet multiple times, as long as he has the money to do so.

EXPLANATION:

The cost of buying a sweet in this case is:

A[i ] - B[i]

So what we can do is create another array of A[i] - B[i] and sort it in increasing order. Then for each i, we would first check if the A[i] value of the sweet is greater than the money we have left with us. If its greater than R then we cannot buy that sweet and we skip to the next one otherwise we can buy the sweet i. At this point the i_{th} sweet is also the cheapest sweet we can buy so we should buy as much of i_{th} sweet as possible. Thus we need to calculate for amount R, how many sweets of type i, we can buy. We can buy sweets till R is greater than or equal to A[i].

sweets\_count = \frac{R - B[i]}{A[i] - B[i]}

we would add this to our answer and move on to the next sweet. Also we would reduce our R by sweet\_count \times (A[i]-B[i]), i.e

R = R - sweet\_count \times (A[i]-B[i])

TIME COMPLEXITY:

O(NlogN) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like

why b[i] is kept aside? I am confused with a[i] - 1 instead.

Can anyone tell why my solution is giving TLE for the first test case while for all the other test cases my submission is accepted?

Link to my submission :-
https://www.codechef.com/viewsolution/63803974

Is it a language specific problem as I am using JAVA?

Can someone point out how wrong was I? (P.S. I am a beginner)

import numpy
for t in range(int(input())):
    n,r=map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    l = []
    for i in range(n):
        l.append(a[i]-b[i])
    ans=0
    q=sorted(range(len(l)),key=l.__getitem__)
    i=0
    m=q[i]
    while(r>=a[m]):
        m=q[i]
        r=(r-a[m])+b[m]
        ans+=1
        if r<a[m]:
            m=q[i+1]
    print(ans)

Can someone please explain why did they write “R-B[i]” instead of just “R” in
sweets_count = R−B[i] / A[i]−B[i]

4 Likes

because We can buy sweets till R is greater than or equal to A[i].
If you just write R then it means you have already decided that you will buy all the sweets of this kind only which will result in WA.

2 Likes

a warm hello to our coders community!! I am a beginner level coder so i just want your help to please guide me in this buysweet problem. My code isn’t able to pass 2 testcases and i cant find my mistake in my algo or code. So its my humble request to please guide me … :pray:
here is my code:- Solution: 63850976 | CodeChef
plz look into it and provide your valuable feedback(the 2 testcases) if u can…

Consider this input:

1
6 3
3 3 5 4 5 3 
1 1 3 3 2 1

Expected Output

1

Your Output

0
1 Like

thanks a lot… it helped i corrected my mistake and my code is submitted successfully :innocent: :hugs:

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define PI 3.141592653589793238462
#define MOD 1000000007
#define lli long long int
#define INF 1e18
#define nl ‘\n’
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define py cout << “YES” << nl
#define pn cout << “NO” << nl
#define loop(i,a,b) for (int i = a; i <= b; i++)
#define rloop(i,a,b) for (int i = a; i >= b; i–)
#define tc(t) int t; cin >> t; while (t–)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))

#define us unordered_set
#define um unordered_map
#define ll long long
#define ull unsigned long long
#define maxpq priority_queue
#define pii pair<int, int>
#define minpq priority_queue<int, vector, greater >

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
void google(int t) {cout << “Case #” << t << ": ";}
template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.f); cerr << “,”; _print(p.s); cerr << “}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}

vector<vector> pre(int N){
vector<vector> divs(N);
loop(i, 1, N-1){
for(int j=i;j<N;j+=i)
divs[j].pb(i);
}
return divs;
}

vector sieve(int n) {intarr = new intn + 1; vector vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll add(ll x, ll y, ll m) {ll res=x+y; return res>=m ? res-m:res;}
ll mul(ll x, ll y, ll m) {ll res=x
y; return res>=m? res%m:res;}
ll sub(ll x, ll y, ll m) {ll res=x-y; return res<0? res+m:res;}
ll power(ll x, ll y, ll m) {ll res=1; x%=m; while(y){ if (y&1) res=mul(res, x, m); y >>=1; x=mul(x, x, m);} return res;}

bool mycmp(pair<lli,lli>a,pair<lli,lli>b){
return abs(a.f-a.s)<abs(b.f-b.s);
}

void solve(){

tc(t){
    lli n,k;
    cin>>n>>k;
    lli arr[n],brr[n];
    loop(i,0,n-1){
        cin>>arr[i];
    }
    loop(i,0,n-1){
        cin>>brr[i];
    }
    vector<pair<lli,lli>>vp;
    loop(i,0,n-1){
        vp.pb({arr[i],brr[i]});
    }
    sort(all(vp),mycmp);
    lli num=vp[0].f;
    lli num2=vp[0].s;
    lli c=0;
    while(k>=num){
        k-=num;
        k+=num2;
        c++;
    }
    loop(i,0,n-1){
        if(k>=vp[i].f){
            c++;
            k-=vp[i].f;
        }
    }
    cout<<c<<nl;
}  

}

int main(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

#ifndef ONLINE_JUDGE
freopen(“Error.txt”, “w”, stderr);
#endif

fio;
auto start1 = high_resolution_clock::now();
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast(stop1 - start1);

#ifndef ONLINE_JUDGE
cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}
May I know where my code is failing
and tell me also how i can correct my code to get an AC
verdict

what is the problem writing this
ans+=(r-(v[i].second-v[i].first))/v[i].first;
r=v[i].second-v[i].first;
instead of following
diff = (r - (v[i].second - v[i].first))/v[i].first;
ans += diff;
r -= (diff*v[i].first);

Hello, I wonder whats wrong here :slight_smile:

#include <iostream>
using namespace std;
#define long long ll;

int main() {
     int t;
     cin >> t;
     
     while(t--){
          int n,r;
          int ts =0;
          cin >> n >> r;
          int a[n];
          int b[n];
          
          for (int i = 0; i < n; i++) {
               cin >> a[i];
          }
           for (int i = 0; i < n; i++) {
               cin >> b[i];
          }
          
          for (int i = 0; i < n; i++) {
               for (int j = 0; j<n ; j++) {
                 //    cout << r << " " << a[i] << " " << b[i]  << endl;
               if(r < a[i]){
                    break;
               }
               r = r - a[i] + b[i];
               ts +=1;
               }
             
          }
          cout << ts << endl;
     }
}

instead of println i’ve used print("\n") and it worked for me.

Thank you so much @rajivrtk11 bro it works wow, still can’t believe.
By the way do you know the reason why it was giving TLE just because I am using println?
I thought that sorting function was giving TLE. Never thought a normal println function can give a TLE. Very Strange!!

Input
1
3 4
3 4 5
2 3 4

Output

Expected
2
Actual
0
Can anyone explain me why chef cannot buy any sweet even though he has Rs 4 and a sweet of Rs 3 is available???

I have been whacking my brain on this problem for the past 11 hours please guide me what is the issue with my solution, i will be very grateful : :sweat_smile:

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc =new Scanner(System.in);
int cases = sc.nextInt();
for (int i=0;i<cases ;i++ ){
int sweetnum = sc.nextInt();
int budget = sc.nextInt();
int[] arr =new int[sweetnum];
int cheapsweet =Integer.MAX_VALUE;
int cheapindex=0;
int[] least = new int[sweetnum];
int value = Integer.MAX_VALUE;
int index= 0;
int count=0;

	    for(int j=0;j<arr.length;j++){
	        arr[j]=sc.nextInt();    
	    }
	    
	    int[] cb = new int[sweetnum];
	    for(int k=0;k<cb.length;k++){
	        cb[k]=sc.nextInt();
	        least[k]= arr[k]-cb[k];
	        
	        if(least[k]<value){
	            value=least[k];
	            index=k;
	        }
	    }
	   for(int x=0;x<arr.length;x++){
	        if(arr[x]<=cheapsweet){
	            cheapsweet=arr[x];
	            cheapindex=x;
	            if(arr[x]==cheapsweet){
	                cheapindex=x;
	            }
	        }
	   }		    
	        while(budget>=arr[index]){
	  budget=budget-arr[index];
	   count++;
	  budget=budget+cb[index];
	   
	    }
	    if(budget>=cheapsweet){
	       while(budget>=cheapsweet){
	           budget=budget-cheapsweet;
	           budget=budget+cb[cheapindex];
	           count++;
	       }
	    }		 		   
	   System.out.println(count);
	    } 
}

}

“i” is never getting updated right, in the next iteration your m value will again become q[0] .I think this is the problem with your code.

Hey @passedporn
Thanks for asking your doubt.

There is some logical mistake in your code.
According to your code, you are choosing only one index whose a[i] -b[i] is minimum which is ‘index’. But there can be many such indexes. For example

1
2 100
100 90
90 75

you can buy the first item at 100 and get a cashback of 90 so the total remaining money is 90. Now you cannot buy the first item.

Then you buy the second item at 90 and get a cashback of 75.
Note: To buy any item your remaining money must be less than or equal to a[i] and after buying that item you get a cashback of b[i] so total spending is &a[i] -b[i]&

can anyone please help me what’s wrong in my code I am unable to find my mistake
Thanks in advance

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int o = sc.nextInt();
		while(o > 0){
		    long n = sc.nextLong();
		    long r = sc.nextLong();
		    long a[] = new long[(int)n];
		    long b[] = new long[(int)n];
		    for(long i = 0;i < n;i++){
		        a[(int)i] = sc.nextLong();
		    }
		    for(long i = 0;i < n;i++){
		        b[(int)i] = sc.nextLong();
		    }
		    long[] pq = new long[(int)n];
		    Map<Long, Long> m = new HashMap<Long, Long>();
		    for(long i = 0;i < n;i++){
		        pq[(int)i] = a[(int)i] - b[(int)i];
		        if(!m.containsKey(a[(int)i] - b[(int)i])){
		            m.put(a[(int)i] - b[(int)i], a[(int)i]);
		        }else{
		           m.put(a[(int)i] - b[(int)i], Math.min(m.get(a[(int)i] - b[(int)i]), a[(int)i]));
		        }
		    }
		    Arrays.sort(pq);
		    long i = 0;
		    long count = 0;
		    while(i < n && r > 0){
		        long rest = pq[(int)i];
		        if(r - m.get(rest) > 0){
		            count += ((r - m.get(pq[(int)i])) + 1) / rest;
		            r -= count * rest;
		        }else if(r == m.get(rest)){
		            count++;
		            r -= rest;
		        }else{
		            i++;
		        }
		    }
		    System.out.println(count);
		    o--;
		}
	}
}