# FFL - Editorial

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[1234];
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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}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() {
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[0]+v1[0];
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() {

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[0]+def[0]+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[0]+def[0]+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;
}

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

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[101],n[101];
p[100]=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

#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[100],price[100];
int defar[100], forwar[100];
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[0]+forwar[0]<=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 .