PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Utkarsh Gupta
Tester: Taranpreet Singh
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Cakewalk
PREREQUISITES:
PROBLEM:
Chef wants to make a purchase with X gold coins. He has N fixed deposits, the i^{th} of which is worth A_i coins. Find the minimum number of deposits he has to open, so that he has at least X coins. If it is not possible, print -1.
QUICK EXPLANATION:
- Sort the array in decreasing order.
- Find the smallest prefix with a sum greater than or equal to X.
- If the sum of all elements is less than X, the answer is -1.
EXPLANATION:
Let us consider a situation where we have opened some deposits till now and we still need Y more coins for the purchase. For our next move, let us consider two unopened deposits i and j (i \neq j). Assuming A_i > A_j, it is always optimal to choose A_i instead of A_j, because:
- Y \leq A_j: We can have the required number of coins by opening deposit j. But, since A_i > A_j, choosing deposit i would also complete the goal in a single move only.
- A_j < Y \leq A_i: Opening deposit j only would not be sufficient. We would need more deposits to complete the goal. However, if we choose deposit i, we do not need to open any more deposits. Thus, choosing deposit i is better.
- A_i < Y: We need to open more deposits to complete the goal. However, if we choose deposit i, we would require only Y - A_i more coins which is lesser than Y - A_j coins. This means that we would have to open lesser (or equal) number of deposits to reach the goal.
To conclude, for each move, we choose the unopened deposit with most coins in it. To implement this, we can sort the array in descending order and keep a sum of all the elements we have seen. As soon as the sum reaches X, we can print the answer, which is, the number of elements seen until now.
If the sum of all the elements in the array is less than X, we can’t reach sum X even after opening all the deposits. Thus, the answer is -1 in this case.
TIME COMPLEXITY:
The complexity for sorting the array is O(Nlog(N)) and that of traversing the array is O(N). Thus, the overall complexity of the array is O(Nlog(N)).
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define int long long
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
int t;
assert(1<=t && t<=100);
cin>>t;
while(t--){
int n, x;
cin>>n>>x;
assert(1<=n && n<=100);
assert(1<=x && x<=10000);
int a[n];
for(int i =0 ;i<n;i++){
cin>>a[i];
assert(1<=a[i] && a[i]<=100);
}
sort(a, a+n);
int ans = 0, sum =0 ;
while(sum < x && ans < n){
ans++;
sum += a[n-ans];
}
if(sum >= x) cout<<ans<<endl;
else cout<<-1<<endl;
}
}
Tester's Solution
import java.util.*;
import java.io.*;
class MINFD{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), X = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
Arrays.sort(A);
int ans = 0;
for(int i = N-1; i>= 0 && X > 0; i--){
X -= A[i];
ans++;
}
if(X <= 0)pn(ans);
else pn(-1);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MINFD().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007
int n, x;
void solve()
{
cin>>n>>x;
vector<int> a(n);
for(int i = 0; i<n; i++){
cin>>a[i];
}
sort(a.rbegin(), a.rend()); //reverse sort the vector
int sum = 0;
for(int i = 0; i<n; i++){
sum += a[i];
if(sum >= x){
cout<<i+1;
return;
}
}
cout<<-1;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}