ASHIGIFT - editorial

PROBLEM LINK:

Practice

Contest

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:

author

tester

editorialist

4 Likes

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:


[1]


  [1]: http://www.codechef.com/viewsolution/6593138
2 Likes

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 :smiley:

My Binary-search based solution gave WA for one testcase in both categories (30 and 70).
Finally the DP worked!

Nice editorial… very good explanation… thank you very much

can any body tell me why this is giving wrong answer

http://www.codechef.com/viewsolution/6600544

your code would not work for following test,

4
1 3 1
1 2 1000 0

actual ans = 2

Moreover greedy approach is wrong.

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?


I am continuously getting WA for 2nd subtask. Can anyone provide me a test case to get it AC?

https://www.codechef.com/viewsolution/19060197
can anyone tell y am i getting wrong answer. Thanks in advance