PRICECON - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Link

Author: Aryan Agarwala
Tester: Felipe Mota
Editorialist: Rajarshi Basu

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

Chef has N items in his shop (numbered 1 through N) for each valid i, the price of the i^{th} item is P_i. Since Chef has very loyal customers, all N items are guaranteed to be sold regardless of their price.

However, the government introduced a price ceiling K, which means that for each item i such that P_i>K, its price should be reduced from P_i to K.

Chef’s revenue is the sum of prices of all the items he sells. Find the amount of revenue which Chef loses because of this price ceiling.

EXPLANATION:

Just simulate whatever is said!
Let’s say the loss in income for Chef is given by the variable loss.
For every element in the array P_i, the price at which it will be sold at is max(P_i, K). (think why?)
Thus, for every element i,
loss= loss + (P_i - max(P_i,K))

The complexity for this solution is O(N), as for every i, we only do a max operation, and a subtraction.

SOLUTIONS:

Setter's Code 
#include <bits/stdc++.h>
#define int long long
#define INF 10000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
using namespace std;
signed main(){
    int t, n, k, num, ans;
    cin>>t;
    while(t--){
        cin>>n>>k;
        ans = 0;
        for(int i = 0;i<n;i++){
            cin>>num;
            ans+=max((int)0, num - k);
        }
        cout<<ans<<endl;
    }
    return 0;
}
Tester's Code 
t = int(raw_input())
while t > 0:
    n, k = map(int, raw_input().split())
    print sum([max(x - k, 0) for x in map(int, raw_input().split())])
    t -= 1

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

2 Likes
2

If any new user are there …who want to learn from basics then,
This will help you a lot :
Just Go through This

Please Subscribe my channel Hello World .

3

nice

4

check out all LONG CHALLENGE problems’ solutions here

5

Can u please explain this line. I know this is a basic line but i am new to cp.
" ans+=max((int)0, num - k);"
Because you have said in the explanation that
loss+=pi-max(pi,k);
but here u have done the above line. Please explain

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

int main() {
    int t;
    cin >> t;
    while(t--){
        long int n,k,p,ans = 0;
        cin >> n >> k;
        
        while(n--){
            cin >> p;
            if(p>k)ans+=p-k;
        }
        
        cout << ans << '\n';
    }
}
3 Likes
7

loss only if num>k or num-k >0

if num<=k then its normal price , hence no loss,
thus (num-k) is negative

loss+ (-ve number) =>profit ??? whis is wrong as it will compensate previous loss
to avoid this max (0,difference)

8

Thank you.

9

thanks

10

June long challenge editorial beginner friendly video explanation

Delicious cake (CONTAIN) : Codechef June Long Challenge||The Delicious Cake(CONTAIN) - YouTube
Tom and jerry (EOEO) : CodeChef June Long Challenge||The Tom and Jerry Game!||EOEO - YouTube
Even matrix (EVENM) : CodeChef June Long Challenge||Even Matrix|| EVENM - YouTube

11

video Explanation

12

loss += pi - max(pi, k)

if pi is maximum then
pi <== max(pi, k)
loss += (pi - pi)
loss += 0 -------------(1)
else
k is maximum then
k <== max(pi, k)
loss += (pi - k) --------------(2)

so loss += max( (1) , (2) )
this is same as
loss += max(0, pi-k)

I hope you will understand