Problem-Click here
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.
A solution at github- Click here
You can look at this solution or you can explain your approch.
Can anybody tell a solution and explain why it works.
Thank you so much in advance!
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.
I understood this much but i wanna ask , Is the solution possible without powers of two and considering something else.
@galencolin?
I mean, you can also just do the “normal way” to do binary search, as many would say. I don’t see any advantage to the power of 2 thing.
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.
log 10^18 is 60 so if we ignore it doesn’t really matter.Right?
I mean, 60 is pretty big, especially when it’s an additional factor onto some O(n\log{n}) or even O(n\sqrt{n}) algorithm
Because 60 is more than 10 times(its adding one more zero).Right?
I guess I should clarify what I mean by “big”
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.
I got a clear cut idea from your explaination. Thank you so much for such effort legend!
I’m not a legend yet, we’ll see if I become red tomorrow (today in your timezone?)
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?
That’s kinda interesting, what’s the 10% you usually miss?
i lack at writing code faster like the solution is in my mind.But i lack at implementation and speed!
Any Suggestion you wanna give i will be glad!