GFTSHP - Editorial

editorial
, , , ,
1

PROBLEM LINK:

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

Setter: Pranav Dev
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

Chef wants to impress Chefina by giving her the maximum number of gifts possible.

Chef is in a gift shop having N items where the cost of the i^{th} item is equal to A_{i}.
Chef has K amount of money and a 50 \% off discount coupon that he can use for at most one of the items he buys.

If the cost of an item is equal to X, then, after applying the coupon on that item, Chef only has to pay {\bf \left\lceil \frac{X}{2} \right\rceil} (rounded up to the nearest integer) amount for that item.

Help Chef find the maximum number of items he can buy with K amount of money and a 50 \% discount coupon given that he can use the coupon on at most one item.

EXPLANATION:

Let M be the maximum number of items that Chef will buy, and let \{i_1, i_2, \ldots i_M\} be the list of items that costs minimum among all possible list of items of size M. Also, let S = \sum_{\alpha = 1}^{M} A_{i_{\alpha}}

Observation 1: Chef will always use the discount coupon on the most expensive item. This is because the amount of money that Chef will pay will be S - discount, and as the price increases, the discount increases.

Observation 2: The list of items will have the M lowest priced items. To prove this, let us introduce a new item j in the list of items and remove i_\alpha such that A_{i_\alpha} < A_j. We can make 4 cases on {discount on A_{i_\alpha}, discount on A_{j}} and in each case, we can see that the original list results in less overall cost.

So we can first sort the items in the increasing order of price, and for each i such that 1 \leq i \leq N, check if we can take first i elements by applying discount on the i^{th} item. The largest feasible i will be our answer.

TIME COMPLEXITY:

O(N \cdot \log{N}) for each test case.

SOLUTION:

Editorialist's Solution 
#define ll long long
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
using namespace std ;


void solve()
{
    ll n , k ;
    cin >> n >> k ;

    ll arr[n] ;
    for(int i = 0 ; i < n ; i++)
        cin >> arr[i] ;
    sort(arr , arr+n) ;

    ll sum = 0, ans = 0;

    for(ll i = 0 ; i < n ; i++)
    {
        ll new_cost = (arr[i] + 1)/2 ; // ceil division
        if(sum + new_cost <= k)
        {
            ans++ ;
            sum += arr[i] ; // updating sum for next iteration
        }
        else
            break ;
    }

    cout << ans << '\n' ;
    return ;
}

 
int main()
{   
    
    ll t = 1 ;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}
2

Can you please explain why are you using new_cost as 50% discount for again and again? Because in the question, its given that we can use that coupon for at most one item.

2 Likes
3

If you review the items in ascending order, if you can afford the next item at full price from your remaining budget, it is always acceptable to pay that to get the maximum gifts solution.

Why? Because either you can afford the next more expensive item at half-price, or you can’t, but there’s no benefit to taking the current affordable item at half price because it won’t make it easier to afford subsequent items.

4

What is that line which is written just before return 0 statement.
What is its role, what is that syntax??

5 
tc  = int(input())
for i in range(tc):
  next_line = input()
  n, k = list(map(int, next_line.split()))
  next_line = input()
  prices = list(map(int, next_line.split()))
  sorted_prices = sorted(prices)
  cost = 0
  j = 0
  while j < n:
    if cost + sorted_prices[j] > k:
      break
    cost += sorted_prices[j]
    j += 1

  if cost + round(sorted_prices[j] / 2) <= k:
    j += 1
  print(j)

I am getting the Runtime Error (NZEC) for 2 of the 3 tasks for this solution. Any idea why this error could occur in the above code.

6 
#include <iostream>
#include<algorithm>
using namespace std;
int Discount(int a)
{
float x=a/2;
if(x-(a/2)<0.5) return (a/2);
else return ((a/2)+1);
}
int ITEMS(int a[],int n,int k)
{
int i,ans=0;
for(i=0;i<n;++i)
{
if(k>a[i])
{
k=k-a[i]; ans++;
}
else
{
if(k>=Discount(a[i]))
{
++ans;
break;
}break;
}
}
return ans;
}
int main()
{
int t; cin>>t;
while(t–)
{
int n,k; cin>>n>>k;
int a[n];

    for(int i=0;i<n;++i) cin>>a[i] ;
    
    sort(a,a+n);
    cout<<ITEMS(a,n,k)<<endl;
}
return 0;
}

can anyone say the mistake in the code?

7

look at the solution carefully… we are just checking the discount for the current item…we are actually adding a[i] in sum and not new_cost which means we are providing discount only once

1 Like
8

O yes… Now I got it. I was doing the same approach using C, but got TLE for the last task. Maybe my sorting algo was taking too much time

9

It is the cerr command which is used in this case to print the time taken (of course this won’t be treated as output) but just to be safe people want to check so that they won’t get TLE.

10

/*#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#define endl “\n”

void solveTestCase()
{
ll N, K;
cin >> N >> K;
ll A[N];
for (int i = 0; i < N; i++)
cin >> A[i];

sort(A, A + N);

int i = 0;
while (K > 0 && i < N)
{
	if (A[i] > K)
	{
		if ((A[i] / 2) + 1 <= K)
		{
			i++;
		}
		break;
	}
	K -= A[i];
	i++;
}
cout << i << endl;

}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int testCases;
cin >> testCases;
while (testCases–)
{
solveTestCase();
}

return 0;

}
*/
Why it is giving WA in first 2 testcases and passed in third Testcase ??

1 Like
11

In the case when all items can be purchased, your final if statement will attempt to check beyond the end of available items. You could instead check this condition within the if statement that is inside the while loop

12

(A[i] / 2) + 1 will give the wrong answer for checking discount on even-priced items.

13

@joffan but the max number of gifts available in the shop is equal to n which in the while loop I am checking. So it shouldn’t check beyond it.

14

Check your rounding strategy.

15

After your while loop, you are not checking whether j < n or not.
Maybe accessing sorted_prices[n] resulted in array index out of bounds error.

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

int main() {
    long long int t;
    cin>>t;
    while(t--)
    {
        long long int n,k,count=0,sum=0;
        cin>>n>>k;
        vector <long long int> v;
        for(long long int i=0;i<n;i++)
        {
            long long int l;
            cin>>l;
            v.push_back(l);
        }
        sort(v.begin(),v.end());
        long long j=accumulate(v.begin(),v.end(),0);
        if(j<=k)
        {
            cout<<n<<endl;
        }
        else
        {
            for(long long int i=0;i<v.size();i++)
            {
                sum=sum+v.at(i);
                if(sum<=k)
                {
                    count++;
                }
                else 
                {
                    sum=sum-v.at(i);
                    sum=sum+round((double)v.at(i)/2);
                    if(sum<=k)
                    {
                        count++;
                    }
                    i=v.size();
                    }
                }
                cout<<count<<endl;
            }
        }
	// your code goes here
	return 0;
}

I am getting the desired output but on submitting the above code WA is being returned can anyone please tell me what’s wrong with the above code.

17

Thanks

18

As I said, the test I’m talking about is after the while loop. Your index has (potentially) gone out of range.

I’m wondering if you tried the sample input for the problem. The second case given there allows all items to be purchased full price, which breaks your code.

19

def main():

testcases=int(input())

for test in range(testcases):
    
    n,k=map(int,input().split())
    
    


    l=list(map(int,input().split()))
    
    l.sort()
    
    
    index=0
    
    s=0
    
    count=0
    
    for i in range(n):
        
        
            
        s+=l[i]
        
        if s>k:
            break
        
        count+=1
    
    s=s-l[i]

    if count==n:
        
        print(n)
        
    else:
        
        a=ceil(l[i]/2)
        
        if s+a<=k:
            
            print(count+1)
            
        else:
            
            print(count)

My solution in Python

20

@joffan @adithya5768 Thanks a lot. Able to figure the issue now.
But I am still getting WA for few test cases. Below is the updated code.

tc  = int(input())
for i in range(tc):
  next_line = input()
  n, k = list(map(int, next_line.split()))
  next_line = input()
  prices = list(map(int, next_line.split()))
  sorted_prices = sorted(prices)
  cost = 0
  j = 0
  while j < n:
    if cost + sorted_prices[j] > k:
      break
    cost += sorted_prices[j]
    j += 1

  if (j < n):
    if (cost + round(sorted_prices[j] / 2) <= k):
      j += 1
  print(j)