Can Anyone explain a solution to this problem.I have seen solutions on github and analyzed it much.But i am not getting the reason why that particular solution is working.i am just Confused.

They (github sol) are binary searching on the answer. The first half of the code is determining the upper bound for binary search, then the second half is doing it.

Do you understand how to solve the decision problem - that is, given a time x, is it possible to make at least t products with only x units of time?

If we are given the time taken to make one product then its possible to tell whether we can make t products or not!am i right?

Can you elaborate that github solution that why only powers of two helped in making a solution to that problem?I am just confused in that solution. @galencolin
Thanks in Advance!

Itâ€™s an unconventional way of writing binary search, but itâ€™s the same principle.

You start off with an answer in the range [0, 2^k]. You see if 2^{k - 1} is possible. If so, your answer is now in the range of [2^{k - 1}, 2^k], otherwise itâ€™s in [0, 2^{k - 1}]. Now you have another interval, also with its size being a power of 2, and you can repeat the process.

Can you elaborate normal binary search approach ,
i mean how do we then calculate upper bound in a normal way (without power of two) and proceed further with that approach? @galencolin

You donâ€™t really need to calculate the upper bound. The worst-case time requirement would be for a single machine that requires 10^9 seconds, with t = 10^9. So the upper bound can be 10^{18}.

Doing it this way, though, requires you to have to be careful of overflow when doing calculations.

I got accepted using this method.Time Complexity will be O(n) right?
because whatever the input is , it will take only 60 iterations in finding the solution(binary search),so it is a constant.
so Time Complexity will be O(n) Right? @galencolin

I write complexities â€śinformallyâ€ť, so I would probably write it as O(n \log{10^{18}}), but O(n) is the correct mathematical complexity since 10^{18} is fixed. I personally feel like the \log{10^{18}} is too big of a constant to ignore, and itâ€™s a significant part of the algorithm, so it seems like it should be included. But honestly, it doesnâ€™t really matter, as long as you understand the magnitude of the number of operations done.

I think \log{10^{18}} is important because itâ€™s based on a constraint on the input. 10^{18} was a derived number based on the input constraints being 10^9. If the input was instead 10^4 or something, then the corresponding \log{10^8} could also be considered important.

Whatâ€™s not big is stuff like algorithmic details. For example, see the github solution. It has two O(n \log{10^{18}}) loops, but I donâ€™t include the 2 because itâ€™s based on the algorithm and not the input.

Uhhâ€¦ I can see this getting more and more unclear by the second. I guess order-of-magnitude factor of 10 is an okay rule of thumb for â€śbigâ€ť, since the most detail you should really put into time complexity should be some quick calculation. For example, something like â€śthis algorithm will take around 5 \cdot 10^7 operations, which is fine for 2 secondsâ€ť. Maybe thereâ€™s some extra constant in there somewhere, maybe itâ€™s actually half that, but it wonâ€™t matter unless youâ€™re cutting it really close to TL.

To keep in mind, this is all my preference. Youâ€™re free to think about complexity however you want.

Yes Today in Indiaâ€™s Timezone.I wish you become red!
Can You give some tips for me to become better at solving problems @galencolin?
I am always 90% there in the solution but that i lack that 10%.
Can you give some tips so that i can improve fast?