Certain problems required us to try all the possible solutions to find the one that best fit the given constraint, a very popular brute force way is to perform a complete search of the solution space by iterating over and over the data and changing each time the input variables.
If the problem require to calculate the maximum or minimum number of ways to perform a certain action (assuming we’re not dealing with a linear programming problem), then again a brute force solution –may- consist on performing the action one, two, three…N times, where N is the best outcome.
There’s one problem solving technique that everybody should know very well since is that simple and still extremely powerful, the idea behind it is not search for the input which allows to obtain the best solution by trying to build the best solution, but instead search between all the solutions the one which for the given constraint is the best, and then from this best solution search for the input which allows to obtain it.
As a sake of an example, let’s assume you are a recruiter from Guuglu a big and venerable IT company which is looking to hire a smart engineer, the recruiter already have an ideal candidate for which is preparing a job offer, only the correct salary proposal is missing.
To determine the best salary, the recruiter with the hiring manager decided to develop an algorithm which will calculate how much should be offered to that engineer, they don’t want to pay too much nor too less, but exactly the right amount of money which will make the engineer happy, nothing more!
Guuglu has a long tradition of perfect salary decisions, so they don’t want to ask the candidate how much he want, he may ask for much more than he really want after all. They want to find the best salary by trial and error!
The recruiter suggest to iterate from a minimum salary of one dollar a year till the maximum amount the company is willing to pay, somewhere in between the engineer will smile and accept the proposition!
So we have the recruiter calling the candidate every day with a new offer, every time slightly higher than the last one: 1,2,3…10000…100000USD and bingo! After one hundred thousand iterations the deal is done!
Did Guuglu solved the problem? Yes! Did Guuglu hired the engineer? Yes! Can this operation be performed faster? YES! After all, the recruiter called everyday the candidate with a new offer for one hundred thousands days, or 273 years, at that point the milestone for the important project for which he was recruited may be missed long time ago.
To do better the recruiter can follow a different strategy, to find the best salary he may want to call the candidate offering him the extraordinary salary of one million dollar a year! The engineer is very happy and ready to accept the offer, but the recruiter ask him to way till tomorrow.
Then the recruiter call again with a new offer,this time five hundred thousand dollar! (This engineer is so passionate about Guuglu that he already forgot that the day before the offer was much higher!) Again he accepted, but, the recruiter call again the day after with a new offer: 250000, then 125000 and the fifth day he call and propose 62500, this time the offer is rejected! Now the recruiter know that the best salary is somewhere between 62500 and 125000.
As you already understood, the salary problem is solved by a binary search on the range of all the possible solutions! How simple is that? The only problem is to identify when this technique can be used, I’m writing this post since in the last SRM on codeforces one of the problem was perfectly tailored for this solving technique!
The problem “Magic Powder” is divided in two parts (PART1, PART2), one which can be easily solved with a brute force approach, the second part which has much higher constraint and for which the binary search technique is required.
This is the code which work just fine with the part one of the problem:
int main()
{
ios_base::sync_with_stdio(false);
get(n);
get(k);
readv(0,n,cookie);
readv(0,n,ingred);
ll missing{0},ans{0};
bool boke{true};
std::vector tmp_ing(n);
while(1){
fori(0,n){
if(cookie[i]>ingred[i]){
missing = cookie[i]-ingred[i];
if(missing>k){
boke = false;
break;
}else{
k -= missing;
missing = 0;
}
tmp_ing[i] = 0;
}else
tmp_ing[i] = ingred[i] - cookie[i];
}
if(boke){
++ans;
std::swap(tmp_ing,ingred);
}else break;
}
cout<<ans<<endl;
return 0;
}
That magic macros are absolutely to be avoided in any real/fake project, never ever write stuff like that in anything else than a competitive programming program! People do use those kinda of macros since they allows a much faster typing, the code of the macros (my personal macros) is the following:
#define fori(start,end) for(size_t i{start};i<end;i++)
#define forj(start,end) for(size_t j{start};j<end;j++)
#define foralli(data) fori(0,data.size())
using ll = long long;
constexpr ll LL10{ 10000000000 + 1 };
#define get(var_name) ll var_name{0}; cin >> var_name;
#define readv(start,end,vec_name) std::vector vec_name(end); for(size_t i{start};i<end;i++) cin>>vec_name[i];
You don’t really have to see my full set of macros tough! 🙂
The brute force approach works well and for the part one of it performs also pretty good, but as you can see what basically I’m doing is searching for the solution like our recruiter was trying to do in his first approach, that’s a miserable approach if the numbers get high!
The much faster solution which make use of the binary search technique is the following:
bool check(vll cookie,vll ingred,ll k,ll num){
foralli(cookie){
ll delta = ingred[i] - cookie[i]*num;
if(delta<0){
delta*=-1;
if(delta<=k){
k -= delta;
}else{
return false;
}
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
get(n);
get(k);
readv(0,n,cookie);
readv(0,n,ingred);
ll l{0},r{LL10};
while(l<=r){
ll m{(l+r)/2};
if(check(cookie,ingred,k,m)){
l = m + 1;
}else{
r = m - 1;
}
}
cout<<r<<endl;
return 0;
}
As you can see I first check whether is possible to make five billions cookies, then the value is halved , &c &c. This code solve the problem in O(lg(n)), which is a very good bound. the function check, just check whether is possible to make the required num cookies with the available ingredients.
Try to solve yourself this problem, I think it will be very educative and this problem is perfect to learn this important and easy technique.
Well, hope to find the time to complete the second part of my post of suffix trees soon, had a lot of things going on those days and not very much free time, hope you enjoyed this short post, thanks for reading!