Sung Jin-woo vs Magic Beasts

Author: naveentummala033

Required Knowledge : Binary Search, Greedy

Time Complexity : $O(M \cdot log_2M)$

Editorialist : naveentummala033

Approach:

Before finding minimum number of commands required, let us first check if it is possible to kill all the magic beasts using all $M$ commands. We will try to deal the final blow to the beast using the last index occurence in command array. This means that the commands having that index before the last occurence will be used to decrease the health of the magic beasts. Thus, whenever we get last index occurence we have to check if the number of commands - number of last indices till then were sufficient to kill magic beasts whose last indices occurred till there. If it wasn't sufficient then we can print $-1$. Also if all indices are not there in the commands array then it is not possible.

The above approach can be used to determine if $X$ commands is enough to kill the magic beasts. If $X$ commands were enough then of course more than $X$ commands will also be enough. Also if $X$ commands were not enough then less than $X$ commands also won't be enough.

Thus, we can do binary search and check if $mid$ commands is possible. If possible then go to left side else right side. This way we can get the minimum number of operations.

Setter's Code:

// Author : Naveen

// Program Start
// Libraries and Namespace Start
#include <bits/stdc++.h>
using namespace std;
// Libraries and Namespace End

//----------------------------------------------------------------

// Important Shortcuts Start
// Macros Start
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
// Macros End


// Declarations Start
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
// Declarations End

// Constants Start
const char newl = '\n';
// Constants End

//----------------------------------------------------------------

// Solution Class Start
class Solution {
public:
    bool func(vll& arr, vll& change, ll n) {
        vll last_index(arr.size() + 1, -1);
        for (ll i = 0; i < n; ++i) {
            if (change[i] > 0) {
                last_index[change[i]] = i;
            }
        }
        for (ll i = 1;i < last_index.size();i++) {
            if (last_index[i] == -1) {
                return false;
            }
        }
        ll sumi = 0, cou = 0;
        for (ll i = 0;i < n;i++) {
            if (change[i] > 0 && i == last_index[change[i]]) {
                sumi += arr[change[i] - 1];
                cou++;
            }
            if (i + 1 - cou < sumi) {
                return false;
            }
        }
        return true;
    }
    void solve(ull index) {
        //----------------------------------------------------------------

        ll n, i, j, m;
        cin >> n >> m;
        vll arr(n), change(m);
        for (auto& i : arr) {
            cin >> i;
        }
        for (auto& i : change) {
            cin >> i;
        }
        if (!func(arr, change, change.size())) {
            cout << -1 << newl;
            return;
        }
        ll low = 1, high = change.size();
        ll ans = high;
        while (low <= high) { // binary search on commands
            ll mid = (low + high) / 2;
            if (func(arr, change, mid)) { // function to check if possible or not
                ans = mid;
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        cout << ans << newl;

        // cout << "Case #" << index << ": " << ans << newl;

        //----------------------------------------------------------------
    }

    bool test_cases = true;
};
// Solution Class End

// Main Function Start
int main() {
    Solution sol;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ull test_cases = 1;
    if (sol.test_cases) {
        cin >> test_cases;
    }
    for (ull test_case = 1; test_case <= test_cases; ++test_case) {
        sol.solve(test_case);
    }
    return 0;
}
// Main Function End
// Program End
//----------------------------------------------------------------

Tester's Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element

bool ispossible(ll x,vll & a,vll & b)
{
    ll n=a.size();
    if(x<n)return false;
    ll i;
    vll lastocc(n,-1);
    for(i=0;i<x;i++)
    {
        if(b[i]!=0)
        lastocc[b[i]-1]=i;
    }
    ll cnt=n;
    ll val=0;
    for(i=0;i<x;i++)
    {
        if(lastocc[b[i]-1]==-1)return false;
        if(b[i]==0)val++;
        else
        {
            if(lastocc[b[i]-1]==i && a[b[i]-1]<=val)
            {
                val-=a[b[i]-1];
                cnt--;
                if(cnt==0)return true;
            }
            else
            {
                val++;
            }
        }
    }
    return false;
}

void solve()
{
    ll n,m;
    cin>>n>>m;
    vll a(n);
    ll i;
    for(i=0;i<n;i++)cin>>a[i];
    vll b(m);
    for(i=0;i<m;i++)cin>>b[i];

    ll ans=-1;
    ll l=1,h=m,mid;
    while(l<=h)
    {
        mid=(l+h)/2;
        if(ispossible(mid,a,b))
        {
            ans=mid;
            h=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}