MXPS-Editorial

PROBLEM LINK:

https://www.codechef.com/WIZC2021/problems/MXPS
Practice link

Author: Hitk Codechef Chapter

Tester: Ankur Kayal

Editorialist: Hitk Codechef Chapter

DIFFICULTY:

SIMPLE.

PREREQUISITES:

Greedy

PROBLEM:

You have to find the maximum no. of elements from the given array whose sum is less than or equal to the given no.

QUICK EXPLANATION:

Sort the array in ascending and traverse the array until the sum of visited elements is less than or equal to the given no.

EXPLANATION:

In this question, you’ve been given ‘n’ different Props cost and ‘x’ that is the amount of money you have to buy the props from.

(Here we would consider the currency as rupee for simplicity although it is some different currency in question it wouldn’t affect the solution.)

In the next line you are given ‘n’ space separated integers which give you the price of different Props. As the aim was to maximize the variety of props, Merlin must’ve sorted the price of all the items and started buying the variety which costs the least.

In the sample input, there are 5 varieties, their cost being [1 2 3 4 5]. He has ₹11. If he buys ₹5 item, he’ll have only ₹6 left using which, naturally he can buy less variety of props. So he first buys ₹1 item and has ₹10 left. As the aim was to maximize variety, he won’t buy ₹1 item again. Then he buy ₹2 ₹3 ₹4 citems. When he has bought these 4 props, he has only 1₹ left but the only variety left is the ₹5 variety which he can’t afford. So you can safely print out 4 as the answer.

Keep increasing a counter which keeps count of the variety when the variety is selected.

The only glitch here would be the array of price which you’ve been given may not be sorted. So don’t forget to sort it in the least time possible. The most efficient sorting algorithm has complexity O( n log n ). Your job’s done.

TIME COMPLEXITY:

O( n log n ).

SOLUTIONS:

Setter's Solution(C++)
    #include<bits/stdc++.h>
    using namespace std;

    #define int long long

    void solve()
    {
        int n, x;
        cin >> n >> x;

        int price_list[n];

        for (int i = 0; i < n; i++)
            cin >> price_list[i];

        sort(price_list, price_list + n);

        int i = 0, total_bill = 0, no_of_chocolates = 0;

        while (i < n && total_bill < x)
        {
            total_bill += price_list[i];
            i++;
            no_of_chocolates++;
        }

        if (total_bill > x)
            no_of_chocolates--;

        cout << no_of_chocolates << endl;
    }

    int32_t main()
    {
        int no_of_test_cases;
        cin >> no_of_test_cases;

        for (int i = 0; i < no_of_test_cases; i++)
            solve();

        return 0;
    }
Tester's Solution(C++)
    #include <bits/stdc++.h>
    using namespace std;

    //----------------------------------- DEBUG -----------------------------------
    #define sim template < class c
    #define ris return * this
    #define dor > debug & operator <<
    #define eni(x) sim > typename \
    enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
    sim > struct rge { c b, e; };
    sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
    sim > auto dud(c* x) -> decltype(cerr << *x, 0);
    sim > char dud(...);
    struct debug {
    #ifdef LOCAL
    ~debug() { cerr << endl; }
    eni(!=) cerr << boolalpha << i; ris; }
    eni(==) ris << range(begin(i), end(i)); }
    sim, class b dor(pair < b, c > d) {
      ris << "(" << d.first << ", " << d.second << ")";
    }
    sim dor(rge<c> d) {
      *this << "[";
      for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
      ris << "]";
    }
    #else
    sim dor(const c&) { ris; }
    #endif
    };
    #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
    // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

    //----------------------------------- END DEBUG --------------------------------

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    #define trav(a,x) for (auto& a : x)
    #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

    //----------------------------------- DEFINES ----------------------------------- 

    #define sz(x) (int)(x).size()
    #define mp make_pair
    #define eb emplace_back
    #define pb push_back
    #define lb lower_bound
    #define ub upper_bound
    #define all(x) x.begin(), x.end()
    #define rall(x) x.rbegin(), x.rend()
    #define ins insert
    #define nl '\n'

    //----------------------------------- END DEFINES -------------------------------- 

    //-------------------------- CUSTOM UNORDERED MAP HASH ---------------------------

    struct custom_hash{
        static uint64_t splitmix64(uint64_t x){
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(uint64_t a) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(a + FIXED_RANDOM);
        }
        template<class T> size_t operator()(T a) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            hash<T> x;
            return splitmix64(x(a) + FIXED_RANDOM);
        }
        template<class T, class H> size_t operator()(pair<T, H> a) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            hash<T> x;
            hash<H> y;
            return splitmix64(x(a.first) * 37 + y(a.second) + FIXED_RANDOM);
        }
    };
    template<class T, class H>using umap=unordered_map<T,H,custom_hash>;

    //----------------------- CUSTOM UNORDERED MAP HASH END--------------------------


    void run_cases() {
        int n,x;
        cin >> n >> x;

        vector<int> a(n);
        trav(u, a) cin >> u;

        sort(all(a));

        for(int i=0;i<n;i++) {
            x -= a[i];
            if(x < 0) {
                cout << i << nl;
                return;
            }
        }

        cout << n << nl;
    }

    int main() {
        ios_base::sync_with_stdio(0); cin.tie(nullptr);

        int tests = 1;
        cin >> tests;

        for(int test = 1;test <= tests;test++) {
            run_cases();
        }
    }

Feel free to Share your approach, if you want to. (even if its same !). Suggestions are welcomed as always had been.