[Google Coding Problem] Help

general
1

This was asked in coding round of Google.

You are given N toys in a shop. The cost of each toy is represented by an array A. You have a C amount of money which you can use to purchase the toys. Also there are K broken toys and you won’t purchase them.

For each Q queries, determine maximum number of toys you can purchase using C amount of money.

Query Definition

  • The first element represents an integer C = Query[i][0]
  • The Second element represents an integer K = Query[i][1]
  • The next K integers representing indices of broken toys.

Example

  • N = 6

  • A = [3,6,2,1,4,5]

  • Q = 1

  • Query = [[10, 2, 2, 5]]

  • C = 10, K = 2

  • Broken toys are represented by indices [2,5]

  • you purchase the toys 1,3 and 6 which cost us a total of A[i] + A[3] + A[6] = 3 + 2 + 5 = 10. Therefore you buy 3 toys using 10 amount of money.

I don’t have the constraints for the problem, i though of applying knapsack dp for each query but this might be TLE. If anyone can suggest any approach or similar problem to practice such problem.

2

This Might Work, Hoping I’m Not Wrong.

  1. Removing Broken Toys from Array
  2. Sorting The Remaining Array

Then
• Consequtive Addition Until The Sum is > or = Money You Have

Or

• Using Binary Search to Check If Sum of Sub-array [0, mid] is >, < or = to Money.
If > Then:
Moving To The Left- part
if < Then:
Moving To The Right-part
if = Then:
You Got Your Answer

If Still >, < After BS:
From Last Index Of BS Start Adding/Subtracting (<, >).
until You Find Sum Which is <=.

3

There are two ways : by seg tree and by not using seg tree

My solution without segtree

#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll                          long long

int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<pair<ll ,ll>>A(n);
        for(int i=0;i<n;i++){
            cin>>A[i].first;
            A[i].second = i;
        }
        sort(A.begin() , A.end());
        unordered_map<ll, ll>new_ind;
        for(int i=0;i<n;){
            ll j=i;
            while(j<n && A[j].first==A[i].first) j++;
            for(int k=i;k<j;k++){
                new_ind[A[k].second] = i;
            }
            i = j;
        }
        
        vector<ll>pref(n, 0);
        for(int i=0;i<n;i++){
            pref[i] = (i?pref[i-1]:0) + A[i].first;
        }
            
        ll q;
        cin>>q;
        while(q--){
            ll c, k;
            cin>>c>>k;
            vector<ll>temp(k);
            for(int i=0;i<k;i++){
                cin>>temp[i];
                temp[i]--;
                temp[i] = new_ind[temp[i]];
            }
            sort(temp.begin() , temp.end());

            ll l=0;
            ll r = lower_bound(pref.begin() , pref.end() , c+1) - pref.begin()-1;
            ll cnt =0;
            ll want = c;
            for(int i=0;i<k;i++){
                if(temp[i]<=r){
                    cnt++;
                    want += A[temp[i]].first;
                    r = lower_bound(pref.begin() , pref.end() , want+1) - pref.begin()-1;
                }
                else break;
            }
            cout<<(r+1)-cnt<<endl;
        }
    }
    return 0;
}
5

is this a sliding window problem?