×

Practice
Contest

Author: Pankaj Jindal, Piyush Kumar
Tester: Sergey Kulik
Editorialist: Aman jain

Simple

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)
}


# 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:
author
tester
editorialist

This question is marked "community wiki".

561412
accept rate: 0%

2561312

 2 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 887●2●7 accept rate: 25%
 0 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 16 accept rate: 14%
 0 My Binary-search based solution gave WA for one testcase in both categories (30 and 70). Finally the DP worked! answered 29 Mar '15, 20:23 5★yash_15 518●1●7●16 accept rate: 2%
 0 Nice editorial... very good explanation... thank you very much answered 29 Mar '15, 23:34 3★sharru05 549●3●23 accept rate: 14%
 0 can any body tell me why this is giving wrong answer http://www.codechef.com/viewsolution/6600544 answered 30 Mar '15, 00:56 1 accept rate: 0% your code would not work for following test, 4 1 3 1 1 2 1000 0 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) abeyaar1★
 0 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 46●2 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×946
×716
×70

question asked: 25 Mar '15, 16:47

question was seen: 2,911 times

last updated: 26 Mar '17, 09:29