PROBLEM LINK: Author: Pankaj Jindal, Piyush Kumar 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 subtask 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:
COMPLEXITY:Binary search takes $O(log(x))$ AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:
This question is marked "community wiki".
asked 25 Mar '15, 16:47

i had a different solution by dynamic programming: The original problem was to find the minimum number of people such that at least one man can reach X. I added a dummy dish at the final point X with y=1 so that now 0 men need to reach the end (after X). Now, i stored all the locations of dishes and tribes in an array and sorted them according to the distance from origin. Let min[i] be the minimum number of people required to reach the end, when starting from ith tribal location. I found this value for all tribal locations starting from the farthest tribe from the origin to the one nearest to the origin. EDIT: there is no need for sorting, since it is given that the elements will be given in the sorted order. So, Complexity : O(B+C) Solution: code answered 29 Mar '15, 17:20

hmm, its a good technique to solve the problem. First, finding the upper limit, then using binary search to get the exact solution. Really enjoyed after solving :D answered 29 Mar '15, 19:26

My Binarysearch based solution gave WA for one testcase in both categories (30 and 70). Finally the DP worked! answered 29 Mar '15, 20:23

Nice editorial... very good explanation... thank you very much answered 29 Mar '15, 23:34

can any body tell me why this is giving wrong answer answered 30 Mar '15, 00:56
your code would not work for following test, 4 actual ans = 2 Moreover greedy approach is wrong.
(01 Apr '15, 17:34)
https://ideone.com/cZDgSY I am continuously getting WA for 2nd subtask. Can anyone provide me a test case to get it AC?
(03 Apr '15, 11:10)

Can you please explain how will the answer be in range [1,X]? X is the distance of byteland from chef's town. In worst case, shouldn't the answer be sum of all yi(no. of people req. to finish a dish)? And can anyone tell me how to solve this problem using dp? answered 02 Apr '15, 01:09

https://www.codechef.com/viewsolution/19060197 can anyone tell y am i getting wrong answer. Thanks in advance answered 03 Jul '18, 21:42
