talisman's blog

Please Help Regarding an EDU Problem
By talisman, history, 3 months ago, In English

I've come across this problem, I know that I'm going to binary search the answer (Given the fact that if x(time) is good, x + 1 is also good), but I am very stuck at how to determine if that time is good or not in the first place. Any help would be much appreciated. Thanks in advance,

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that binary search allows you to change the varying factor.

The original problem requires you to find the minimal T given a fixed m,
which is difficult as you don't know how many balloons to assign for each assistant.

Binary search is essentially choosing a fixed T and finding the maximal m every time,
which is much simpler since the amount of balloons every assistant can inflate in a given time is easy to find.

The way it works is just like what you have mentioned: if they can make m balloons in T minutes, then they must be able to do it in T+1 minutes.
So keep in mind that binary search is transforming one hard problem into log(n) simple problems.

My submission goes here, you are encouraged to write your own solution tho
→ Reply