You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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".

asked 25 Mar '15, 16:47

amanjain110893's gravatar image

4★amanjain110893
561412
accept rate: 0%

edited 16 Jun '15, 11:32

vicky002's gravatar image

1★vicky002 ♦♦
2461312


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

link

answered 29 Mar '15, 17:20

gvaibhav21's gravatar image

7★gvaibhav21
86717
accept rate: 25%

edited 29 Mar '15, 17:35

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

link

answered 29 Mar '15, 19:26

anupam_codecs's gravatar image

3★anupam_codecs
16
accept rate: 14%

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

link

answered 29 Mar '15, 20:23

yash_15's gravatar image

5★yash_15
5081716
accept rate: 2%

Nice editorial... very good explanation... thank you very much

link

answered 29 Mar '15, 23:34

sharru05's gravatar image

3★sharru05
549322
accept rate: 14%

can any body tell me why this is giving wrong answer

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

link

answered 30 Mar '15, 00:56

shivamgarg210's gravatar image

2★shivamgarg210
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) amanjain1108934★

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★

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?

link

answered 02 Apr '15, 01:09

prateekjjw001's gravatar image

4★prateekjjw001
462
accept rate: 10%

edited 02 Apr '15, 01:32

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×780
×594
×67

question asked: 25 Mar '15, 16:47

question was seen: 2,623 times

last updated: 26 Mar, 09:29