2 step buy-sell processes

Revision en4, by TunaMayoSandwich, 2024-07-28 02:02:38

In competitive programming one is sometimes faced with the task to simulate what I call a "buy-sell" (or craft-melt) process where in the first step the player spends a certain amount $$$a$$$ of resources from his budget $$$n$$$ and in the second step he acquires $$$b$$$ units of the resource back by selling what he bought or crafted earlier and, at the start of the process, the relationship $$$ n \geq a > b $$$ stands. While it's relatively simple to derive a formula for the number of items the player is able to buy in total, call it $$$k$$$, one has to be careful not to imply that a negative budget is ever reached during the process.

Take as an example the values $$$n = 10$$$, $$$a = 9$$$ and $$$b = 8$$$. The first approach that came to my mind was $$$k = \frac{n}{a - b}$$$ which in this case gives us a value of $$$10$$$ for $$$k$$$ and obviously doesn't work because the budget is negative multiple times during the process of acquiring ten items. To make sure this doesn't happen it's enough to enforce the budget after the last buy but before the last sell to be non-negative, that is because the budget decreases after each buy-sell operation ($$$a > b$$$), so asking for $$$n$$$ to be non-negative right after the very last buy is the most stringent constraint we can impose and it implies that the budget is non-negative all the way trough (once again, because we lose some money each time, if $$$n \geq 0$$$ after the 10th buy then it also was non-negative after the 9th buy and so on).

$$$n - k \cdot a + (k - 1) \cdot b \geq 0 \iff n - b - k \cdot (a - b) \geq 0 \iff n - b \geq k \cdot (a - b) \iff k \leq \frac{n - b}{a - b}$$$ and thus we arrive to $$$k = \left \lfloor{\frac{n - b}{a - b}}\right \rfloor$$$. As a beginner, this was the best I could do during a recent contest but unfortunately this formula is still flawed because after this amount of operations the remaining budget $$$n$$$ might still be greater or equal to the price $$$a$$$, that is we haven't performed all the buys we could. Let's make sure this doesn't happen by solving the next equation:

$$$n - k \cdot a + k \cdot b \leq a \iff n - a \leq k \cdot (a - b) \iff k \geq \frac{n - a}{a - b}$$$ and thus the final and correct — although I'm eager to getting schooled by the comments — formula is $$$k = \left \lceil{\frac{n - a}{a - b}}\right \rceil$$$. This third formula makes sure we don't leave money unused, but does it ever lead us to a negative balance? We prove it doesn't:

Hp: $$$n, a, b \in \mathbb{N}$$$, $$$n \geq a > b$$$. Th: $$$\left \lceil{\frac{n - a}{a - b}}\right \rceil \leq \left \lfloor{\frac{n - b}{a - b}}\right \rfloor$$$
Proof: $$$\left \lfloor{\frac{n - b}{a - b}}\right \rfloor = \left \lfloor{\frac{n - b + a - a}{a - b}}\right \rfloor = \left \lfloor{\frac{n - a}{a - b} + 1}\right \rfloor = \left \lfloor{\frac{n - a}{a - b}}\right \rfloor + 1 \geq \left \lceil{\frac{n - a}{a - b}}\right \rceil$$$

Have fun using it here 1989D - Кузнечное дело

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English TunaMayoSandwich 2024-07-28 02:02:38 5 Tiny change: 'enforce that the budge' -> 'enforce the budge'
en3 English TunaMayoSandwich 2024-07-26 16:31:49 643 Tiny change: 'it doesn't' -> 'it doesn't.\n\nHp: $n, a, b \in \mathbb{N}$, $n \geq a > b$.' (published)
en2 English TunaMayoSandwich 2024-07-25 20:09:19 2020 Tiny change: '\n\n$n - k*a$' -> '\n\n$n - k \cdot a$'
en1 English TunaMayoSandwich 2024-07-25 19:39:36 402 Initial revision (saved to drafts)