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.
Let us say in a certain round we only spend partial money buying additional k resources, and after that it takes another r rounds to reach the goal. The loss in this round is kp. The gain in next r rounds is rx, where x is the additional productivity. The net gain is therefore rx - kp.
Let us assume this choice is optimal. Then k+1 or k-1 must result in less net gain. Let y be the additional productivity from additional k+1 resources, and z be that from k-1 resources. For k+1, we need to have ry - (k+1)p < rx - kp, i.e., r(y-x) < p. For k-1, we need to have rz - (k-1)p < rx - kp, i.e., r(x-z) > p. Combining the two, we have x - z > p/r > y - x, i.e., 2x > y + z.
Let us say we have m and w resources when we add k-1 resources. If m<=w-2, we will add both additional resources to m for k and k+1, and 2x > y + z implies 2(m+1)w > (m+2)w + mw, which is false. If w-1<=m<=w, we will add one resource to m and one to w, and have 2(m+1)w > (m+1)(w+1) + mw, i.e., w > m + 1, which contradicts the assumption.
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 →
Proof that buy-some is not optimal:
Let us say in a certain round we only spend partial money buying additional
k
resources, and after that it takes anotherr
rounds to reach the goal. The loss in this round iskp
. The gain in nextr
rounds isrx
, wherex
is the additional productivity. The net gain is thereforerx - kp
.Let us assume this choice is optimal. Then
k+1
ork-1
must result in less net gain. Lety
be the additional productivity from additionalk+1
resources, andz
be that fromk-1
resources. Fork+1
, we need to havery - (k+1)p < rx - kp
, i.e.,r(y-x) < p
. Fork-1
, we need to haverz - (k-1)p < rx - kp
, i.e.,r(x-z) > p
. Combining the two, we havex - z > p/r > y - x
, i.e.,2x > y + z
.Let us say we have
m
andw
resources when we addk-1
resources. Ifm<=w-2
, we will add both additional resources tom
fork
andk+1
, and2x > y + z
implies2(m+1)w > (m+2)w + mw
, which is false. Ifw-1<=m<=w
, we will add one resource tom
and one tow
, and have2(m+1)w > (m+1)(w+1) + mw
, i.e.,w > m + 1
, which contradicts the assumption.