 # PROBLEM LINK:

Setter: Shahadat Hossain Shahin
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

Cakewalk

Greedy

# PROBLEM:

Given N available players, each of which is either a defender or a forward player, i-th player having price P_i, find whether Chef can complete his team by buying one defender and one forward player, with only 100 dollars out of which he has already spent S dollars.

# QUICK EXPLANATION

• The dollars available with Chef for defender and forward player is 100-S
• The minimum price to buy a defender is the minimum of the price of all defender players (let’s say min_D), and similarly, the minimum price to buy a forward player is minimum of price among all forward players (let’s say min_F).
• If min_D+min_F \leq 100-S, we have sufficient dollars to buy both a defender and a forward player.

# EXPLANATION

The quick explanation says it all.

First of all, we can check if there is any defender player present among N players. If there isn’t, we can never complete our team. Otherwise, we can find the minimum cost to buy a defender player. Let’s say it’s min_D

Similarly, we can check if there is any forward player present among N players. If there isn’t, we can never complete our team. Otherwise, we can find the minimum cost to buy a forward player. Let’s say it’s min_F

It is easy to see that buying player with minimum cost is optimal, as we need to minimize min_D+min_F

The number of available dollars is 100-S since out of 100, we have only 100-S dollars left.

So, if min_D+min_D \leq 100-S, we have enough dollars to complete the team, the answer is “yes”, otherwise the answer is “no”.

Bonus Problem

Suppose in the above problem, you want to minimize the number of remaining dollars after buying a froward player and a defender, and N \leq 10^5. Can you find the minimum remaining dollars?

Hint

Dynamic Programming

Even bigger Hint

Knapsack DP

# TIME COMPLEXITY

The time complexity is O(N) per test case.

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

const int MAX = 105;

int price[MAX], role[MAX];

int main() {
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
int T;
cin >> T;
for(int t=1;t<=T;t++) {
int n, s;
cin >> n >> s;
for(int i=1;i<=n;i++) cin >> price[i];
for(int i=1;i<=n;i++) cin >> role[i];
string ans = "no";
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
if(role[i] == role[j]) continue;
if((price[i] + price[j]) <= (100 - s)) ans = "yes";
}
}
cout << ans << '\n';
}
return 0;
}

Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983

int p;
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,s;
cin>>n>>s;
int i;
rep(i,n){
cin>>p[i];
}
int min1=1234,min2=1234,val;
rep(i,n){
cin>>val;
if(val==0){
min1=min(min1,p[i]);
}
else{
min2=min(min2,p[i]);
}
}
s+=min1+min2;
if(s>100){
cout<<"no"<<endl;
}
else{
cout<<"yes"<<endl;
}
}

}

Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class FFL{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();int remaining = 100-ni();
int minD = 100, minF = 100;
int[] price = new int[n];
for(int i = 0; i< n; i++)price[i] = ni();
for(int i = 0; i< n; i++){
int type = ni();
if(type == 0)minD = Math.min(minD, price[i]);
else minF = Math.min(minF, price[i]);
}
if(minF+minD <= remaining)pn("yes");
else pn("no");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
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 FFL().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;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always. 2 Likes

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define endl “\n”
#define pb push_back
#define mp make_pair
#define ut unsigned int
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,i,s,r,k=0,m=0,flag=0,ans=0,temp;
cin>>n>>s;
int a[n],p[n];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
cin>>p[i];
vectorv,v1;
for(i=0;i<n;i++){
if(p[i]==1){
v.pb(a[i]);
flag=1;}
if(p[i]==0){
v1.pb(a[i]);
temp=1;}
}
if(flag==0 || temp==0)
cout<<“no”<<endl;
else{
sort(v.begin(),v.end());
sort(v1.begin(),v1.end());
ans=v+v1;
if(ans+s<=100)
cout<<“yes”<<endl;
else
cout<<“no”<<endl;}
}
return 0;
}

whats wrong in this solution…

temp = 0;

1 Like

poor code
" if(ans+s<=100) "

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll n,sum=101,a,b,s,k=101;

vectorcost(n);
vectorpos(n);

void go(){
if(cost.size()==0 || pos.size()==0 ){
cout<<“no”<<endl;
exit(1);
}
for(ll i=0;i<n;i++){
if(pos[i])
k=min(k,cost[i]);
else
sum=min(sum,cost[i]);
}
if(sum+k<=100-s)
cout<<“yes”<<endl;
else cout<<“no”<<endl ;
}

int main(){
void go();
int tc=0;
cin>>tc;
while(tc–){
cin>>n>>s;
for(ll i=0;i<n;i++){
cin>>a;
cost.push_back(a);
}
for(int i=0;i<n;i++){
cin>>b;
pos.push_back(b);
}
go();
}
return 0;
}
//in which case it is giving wrong answer??..and why its a wrong ones…?

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
// your code goes here

ll t,n,s;
cin>>t;
while(t--)
{
cin>>n>>s;
ll i,p[n],d,f,dm=0,fm=0,j=0,pl,ty,k=0;
for(i=0;i<n;i++)
cin>>p[i];
for(i=0;i<n;i++)
{
cin>>ty;
if(ty==0)
{
if(dm==0)
dm=p[i];
else if(dm>p[i])
dm=p[i];
}
else if(ty==1)
{
if(fm==0)
fm=p[i];
else if(fm>p[i])
fm=p[i];
}
}
if((s+fm+dm)<=100)
cout<<"yes"<<"\n";
else
cout<<"no"<<"\n";
}
return 0;


}

Whats wrong in this solution

why is this showing run time error .

#include<bits/stdc++.h>
using namespace std;

int main()

{

ios_base::sync_with_stdio(!cin.tie(0));

int t;
cin>>t;
while(t--)
{
int n,s;
cin>>n>>s;
vector<int> p,d,f;
for(int i=0;i<n;i++)
{
int num;
cin>>num; p.push_back(num);
}

for(int i=0;i<n;i++)
{
int num;
cin>>num;
int temp=p[i];
if(num==0) d.push_back(temp);
else f.push_back(temp);
}

int poss= *min_element(d.begin(),d.end())+*min_element(f.begin(),f.end())+s;
if(poss<=100)cout<<"yes\n";
else cout<<"no\n";

p.clear();
d.clear();
f.clear();
}

return 0;
}

If you calculate minimum by anyother logic it shows either runtime error or wrong answer…

see my siimple code …

#include<bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(!cin.tie(0));

    int t; cin>>t;
while(t--)
{
vector<int>p,def,forw;   // def for defender ,,, forw for forward
int n,s;
cin>>n>>s;
for(int i=0;i<n;i++)
{
int  num;
cin>>num;
p.push_back(num);
}
for(int i=0;i<n;i++)
{
int no;
cin>>no;
if(no==0)
def.push_back(p[i]);   // filling defender
else
forw.push_back(p[i]);   // filling forward
}
sort(forw.begin(),forw.end());
sort(def.begin(),def.end());

int possible= forw+def+s;    // taking minimum of both

if(possible<=100) cout<<"yes\n";
else cout<<"no\n";
}


}

#include<bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(!cin.tie(0));

    int t; cin>>t;
while(t--)
{
vector<int>p,def,forw;   // def for defender ,,, forw for forward
int n,s;
cin>>n>>s;
for(int i=0;i<n;i++)
{
int  num;
cin>>num;
p.push_back(num);
}
for(int i=0;i<n;i++)
{
int no;
cin>>no;
if(no==0)
def.push_back(p[i]);   // filling defender
else
forw.push_back(p[i]);   // filling forward
}
sort(forw.begin(),forw.end());
sort(def.begin(),def.end());

int possible= forw+def+s;    // taking minimum of both

if(possible<=100) cout<<"yes\n";
else cout<<"no\n";
}


}

runtime error

#include<bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(!cin.tie(0));

   int t;
cin>>t;
while(t--)
{

int n,s;
cin>>n>>s;
s=100-s;
int p[n],g[n],d[n],cd=0,cg=0;
for(int i=0;i<n;i++)
{
cin>>p[i];
}
int min1=101,min2=101;
for(int i=0;i<n;i++)
{

int num;
cin>>num;
if(num==0)
{
g[cd]=p[i];         // cd = number of elements in defender
cd++;
}
else
{
d[cg]=p[i];             // cg keeps count of forward ,, no of elements in forward
cg++;
}

}
for(int i=0;i<cd;i++){if(min1>d[i]) min1=d[i];}
for(int i=0;i<cg;i++){if(min2>d[i]) min2=g[i];}

if(min1+min2<=s) cout<<"yes\n";
else cout<<"no\n";
}


return 0;
}

wrong answer

They have not told that there will be atleast 1 defender and 1 forward
But you are doing forw

The team won’t be completed if there is not 1 defender and 1 forward and they have not told that there will be atleast 1 defender and 1 forward 1 Like

What’s wrong with this code??

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int t, n, s;
cin>>t;
while(t- -)
{
cin>>n>>s;
int arr[n], arr1[n];
for(int i=0; i<n; i++)
cin>>arr[i];
for(int i=0; i<n; i++)
cin>>arr1[i];
int min0=INT_MAX, min1=INT_MAX;
for(int i=0; i<n; i++)
{
if(arr1[i]==0)
{
if(arr[i]<min0)
min0=arr[i];
}
else
{
if(min1>arr[i])
min1=arr[i];
}
}
if(s+min0+min1<=100)
cout<<“yes”<<endl;
else
cout<<“no”<<endl;
}
}

Don’t use INT_MAX as you are using integer everywhere and you are doing integer maximum + integer maximum and it is stored in integer

Even I did the same mistake

3 Likes

#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
int n1,s;
int l=100,m=100,p,n;
p=200;
scanf("%d%d",&n1,&s);
for(int i=0;i<n1;i++)
scanf("%d",&p[i]);
for(int i=0;i<n1;i++)
scanf("%d",&n[i]);
for(int i=0;i<n1;i++)
{
if(n[i]==0)
{
int k,temp;
k=i;
if(p[k]>p[l])
{
temp=p[k];
p[k]=p[l];
p[l]=temp;

                }l=k;

}
else
{
int k,temp;
k=i;
if(p[k]>p[m])
{
temp=p[k];
p[k]=p[m];
p[m]=temp;

}m=k;

}

}
if(p[l]+p[m]<=100-s)
printf("yes");
else
printf("no");

}
return 0;


}Whats wrong in this solution?

1 Like

##########################what is wrong in my solution################
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,s,d=0,f=0;
cin>>n>>s;
int a[n],p[n];
for(int i=0;i<n;i++)
cin>>p[i];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
{
if(a[i]==0)//defence player condition
{

            if((s+p[i]<=100)
{
d++;//defence player count
s=s+p[i];//budget after buying a defence player
}

}
else if(a[i]==1)//forward player condition
{

if((s+p[i])<=100)
{
f++;//forward player count
s=s+p[i];//budget after buying a forward player
}

}
if(d==1&&f==1)//if required defence and forward matches
break;//come out of the loop

}

if(d==1&&f==1)
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}

}


}

Not printing answers in new line

thanks bro. i am taking a lot of pressure during the contest which is ruining my performance.

1 Like

PLEASE HELP sample test case passed, but shows wrong on submission . please help me whats wrong in this.
#include<bits/stdc++.h>
using namespace std;
int main()
{ ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
int n,s,sn,i,def=0,forw=0;
int ar,price;
int defar, forwar;
cin>>t;
while(t–)
{
cin>>n>>s;
sn=100-s;
for(i=0;i<n;i++)
cin>>ar[i];
for(i=0;i<n;i++)
cin>>price[i];

for(i=0;i<n;i++)
{
if(price[i]==0)
defar[def++]=ar[i];
if(price[i]==1)
forwar[forw++]=ar[i];
}

sort(defar,defar+def);
sort(forwar,forwar+forw);

if(defar+forwar<=sn)
cout<<"yes"<<"\n";
else
cout<<"no"<<"\n";
forw=0;
def=0;


}
return 0;

}

why it is showing WA if data type is int but showing correct answer if it is long long int …plz reply in FFL question .