Proficient.
Put your skills to the test.

Problem summary

Coins are listed in a fixed order. Find the shortest prefix whose subsets can pay every integer price from 1 through K exactly. Each selected coin can be used at most once in a payment. Print −1 if even all coins are insufficient.

Constraints

N≤100000; K≤1000000; positive coin values≤100000. The source gives no separate bound on T or total N.

Worked example

Original statement sample.

3
7 10
1 2 3 4 5 6 7
3 3
2 4 1
3 6
3 1 4

4
3
-1

Solution analysis

1. For any chosen prefix, sort its coins by value. If all sums 0…covered are attainable, a coin v≤covered+1 extends this interval to 0…covered+v. If the next available coin is larger, covered+1 is impossible.
2. Feasibility is monotone in prefix length: adding coins never removes a possible payment. Binary-search the first feasible prefix. Sort all coins once as (value,originalPosition); a feasibility check scans this sorted list, using only coins whose position belongs to the trial prefix. This avoids sorting repeatedly.
3. For 1,2,3,4,5,6,7 and K=10, the first three coins cover only 0…6. Adding the fourth extends coverage to 10, so answer 4. For 2,4,1 and K=3, the helpful 1 is last: all three coins must be carried, despite only 1 and 2 being needed in an individual payment.

Why it works

The coverage invariant follows by joining the old interval [0,covered] with the interval [v,v+covered] obtained by using the new coin. They touch or overlap exactly when v≤covered+1. A larger first unavailable denomination cannot fill the gap. This proves the feasibility test, and monotonicity proves binary search finds the shortest prefix.

Watch out. Do not reorder which coins are carried: only the feasibility scan is value-sorted. Distinguish covering every price from merely having total value at least K. Duplicates are separate usable coins.

An independently written complete program with standard headers.

// Key idea: The coverage invariant follows by joining the old interval [0,covered] with the interval
// [v,v+covered] obtained by using the new coin. They touch or overlap exactly when v≤covered+1.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
bool feasible(int prefix,int target,const vector<pair<int,int>>&coins){
    long long covered=0;
    for(auto coin:coins){
        if(coin.second>prefix){
            continue;
        }
        if(coin.first>covered+1){
            return false;
        }
        covered+=coin.first;
        if(covered>=target){
            return true;
        }
    }
    return covered>=target;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    while(tests--){
        int n,target;
        cin>>n>>target;
        vector<pair<int,int>>coins(n);
        for(int i=0;i<n;i++){
            cin>>coins[i].first;
            coins[i].second=i+1;
        }
        sort(coins.begin(),coins.end());
        if(!feasible(n,target,coins)){
            cout<<-1<<'\n';
            continue;
        }
        int low=1;
        int high=n;
        while(low<high){
            int middle=low+(high-low)/2;
            if(feasible(middle,target,coins)){
                high=middle;
            }
            else{
                low=middle+1;
            }
        }
        cout<<low<<'\n';
    }
}