PROBLEM LINK:
Author: Pankaj Jindal, Piyush Kumar
Tester: Sergey Kulik
Editorialist: Aman jain
DIFFICULTY:
Simple
PREREQUISITES:
Binary search
PROBLEM:
Poor Chef now wants to go to Byteland. On the way to Byteland he found B tasty dishes, each dish requires B_i people to complete, after eating the dish one can’t move forward. He can ask support from C tribal clans, found on the way, but on one condition by each clan that is, "they will join only if he approaches them with a group of size atleast q_i". Now chef wants to know with what minimum number of people including him he should start his journey to Byteland.
QUICK EXPLANATION:
Binary search over the range of group size Chef can start with and check whether it is possible to reach Byteland with the group size.
EXPLANATION:
Its easy to observe that if there are no tribal clans in the path, then Chef has to start with x = 1+\sum{B_i} people to reach Byteland, first sub-task can be solved using this. But how can he minimize number of people on start when help from tribal clans is available?
Basic idea that might struck to your mind would be to try all possible values in range and check what should be minimum size to reach Byteland, one can easily see that the ans would be in range [1,x], since in the worst case no clan members joins you. Complexity of this solution would be O(x*(B+C)), where B is number of dishes and C is number of tribal clans, that’s about 10^{13} computations which do not fit in our time limit.
If Chef start with x people (including him) and can reach Byteland, then if he starts with more than x people, then also he can reach Byteland.
Let f(n): checks whether its possible to reach Byteland with n people or not. You can do binary search over range [1,x] to find out minimum n such that f(n) is true, as answer would lie in range [1,x] only. For binary searching in a range, the idea is to check value of function in mid point of current range and decide to go to one half depending on its value. This will ensure that in log(x) steps we will reach the optimal value.
Pseudocode:
low = 1, high = x, ans = x
while(low <= high){
m = (low+high)/2
if(possible(m)){
ans = min(ans,m);
high = m-1;
}
else low = m+1;
}
possible(v){
// store dishes and clans in a vector, in increasing order of their distance from Chef's town
// pi,qi,ri are same convention described in problem
for each item in vector:
if item is a dish:
v-=pi
else if v >= qi: v+= ri
return (v>0)
}
</pre>
COMPLEXITY:
Binary search takes O(log(x))
Possible function takes O(B+C)
Total complexity should be O(log(x)*(B+C))
AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:
