Clash Wildcard - Money Heist (CLWI21B) - EDITORIAL

Problem link : Money Heist

Author : Pratyush
Tester: Prajwal

Difficulty: Easy-Medium
Prerequisite: Priority Queue

Problem:
Your task is to find the maximum number of coins that can be grabbed in K minutes by choosing the chest with the maximum number of coins every minute and not choosing the same chest more than B times. You also have to display the chest number chosen every minute.

Hint 1

Take a priority queue where each element has two fields.
First field stores the number of coins.
Second Field stores the the chest number.

Hint 2

Iterate a loop for K times, each time taking the first element of the priority queue and perform operations on it.

Explanation

You have to insert the number of coins and the index number of the chest in the priority queue. The index number stored should be negative as it is mentioned in the question that if multiple chests have the same number of coins then the chest with the lower index should be chosen, so by adding the negative index we can get the chest with the lower index higher up in the priority queue.
Then you have the take the first element in the priority queue and calculate the 1/3rd (ceil value) and decrease that value from the number of coins from that chest as well as add that value to the answer. Also store the index number of the chest selected from the priority queue in a vector. Now remove that element from the priority queue update the array which stores the count for the number of times a chest is chosen so that you can’t choose the chest for more than B times and now push the updated element back in the priority queue.

Problem Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define test unsigned int t;cin >> t;while(t--)
#define fr(n) for(i = 0 ; i < n ; i++)
#define fre(n) for(i = 1 ; i <= n ; i++)
#define pn(x) cout << x <<"\n";
#define ln cout << "\n";
#define ps(x) cout << x <<" ";
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int main()
{
    fastio

    test
    {
        ll n,i,k,ans=0,a,b;

        cin >> n >> k >> b;
        priority_queue<vector<ll>> pr;
        vector<ll> chest;
        ll freq[n+1]={0};

        fr(n)
        {
            cin >> a;
            pr.push({a,-i-1});
        }

        while(k-- && pr.size() != 0)
        {
            ll in = pr.top()[1];
            chest.pb(-in);
            a = pr.top()[0];
            ans+=(ll)ceil(a/3.0);
            a-=(ll)ceil(a/3.0);
            i = freq[-in];
            pr.pop();
            if(a > 0 && i+1 < b)
            {
                freq[-in]++;
                pr.push({a,in});
            }
        }

        ps(ans)
        pn(chest.size())
        fr(chest.size()) ps(chest[i]);
        ln
    }



    return 0;
}
1 Like

Link to my submission using set.
https://www.codechef.com/viewsolution/42216450

2 Likes

can you guys make editorial for this problem of same contest :slightly_smiling_face:
https://www.codechef.com/CLWC2021/problems/CLWI21F

1 Like