We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
a proof that we must only buy-all or buy-none, buy-some is not optimal
At a certain pass, assume that current machine number and worker number is m and w, and m <= w, assume r for (n-remain), if buy-one is better than buy-none means that (r/(m * w))>=((r+p)/(m * w+w)), this equals to r/p >= m
On this basis, prove buying i+1 is better than buying i is to prove that
(r + ip)/(mi * wi ) - (r+ip+p)/(mi * wi + wi) >= 0 where mi, wi is machine number and worker number after investing i times
(r + ip)/(mi * wi ) - (r+ip+p)/(mi * wi + wi) >= 0 equals r/p >= mi - i, because of r/p >= m, we only need to prove m >= mi - i, since i is split into wi and mi, m + i >= mi is obvious.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Making Candies
You are viewing a single comment's thread. Return to all comments →
a proof that we must only buy-all or buy-none, buy-some is not optimal
At a certain pass, assume that current machine number and worker number is m and w, and m <= w, assume r for (n-remain), if buy-one is better than buy-none means that (r/(m * w))>=((r+p)/(m * w+w)), this equals to r/p >= m
On this basis, prove buying i+1 is better than buying i is to prove that (r + ip)/(mi * wi ) - (r+ip+p)/(mi * wi + wi) >= 0 where mi, wi is machine number and worker number after investing i times
(r + ip)/(mi * wi ) - (r+ip+p)/(mi * wi + wi) >= 0 equals r/p >= mi - i, because of r/p >= m, we only need to prove m >= mi - i, since i is split into wi and mi, m + i >= mi is obvious.