What an instalment plan costs
A shop sells an item for S tenge, or on instalments: n monthly payments of P tenge, the first a month after the purchase. The overpayment is plain to see: P · n − S. But how much is that as an annual rate? A buyer who pays in parts does not use the whole sum for the whole term, so dividing the overpayment by the price and by the number of years is wrong.
The honest answer is the effective rate. Find the monthly rate r at which the payments, discounted to the day of purchase, add up to exactly the price:
$$S = \frac{P}{1 + r} + \frac{P}{(1 + r)^2} + \dots + \frac{P}{(1 + r)^n},$$and print the annual rate (1 + r)¹² − 1 in percent.
Input
The first line holds the number of offers q (1 ≤ q ≤ 2000). Each of the next q lines holds three integers S, P, n (1 ≤ S ≤ 10⁹, 1 ≤ P ≤ 10⁹, 1 ≤ n ≤ 360). It is guaranteed that P · n ≥ S and the monthly rate is below 40 %.
Output
For each offer, the effective annual rate in percent. An answer is accepted with an absolute or relative error of 10⁻⁶.
Examples
Example 1
3 600000 29990 24 480000 40000 12 150000 16500 10
19.706249 0.000000 23.457163
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
There is no formula for r: it is a root of an equation of degree n. How does the right-hand side behave as r grows?
2Hint 2
As the rate grows, each payment is worth less “today”, and the sum decreases. At r = 0 it equals P · n ≥ S. So the root is squeezed between 0 and any rate at which the sum is already below S.
3The idea
The present value of the payments PV(r) decreases monotonically, so the monthly rate is found by bisection on [0, 1]: if the PV of the midpoint is greater than the price, the rate is above the midpoint, otherwise below. 80 halvings narrow the interval to 2⁻⁸⁰, finer than a double can hold.
4Walkthrough
The sum of the geometric series is computed by the formula PV(r) = P · (1 − (1 + r)−n) / r, with two precautions. At r = 0 the formula divides zero by zero: this is an instalment plan with no overpayment, and PV = P · n. And at a tiny r the difference 1 − (1 + r)−n loses digits: almost one is subtracted from one. So compute it as −expm1(−n · log1p(r)); the functions expm1 and log1p exist in both Python and Go and keep their accuracy near zero. Likewise the annual rate: expm1(12 · log1p(r)).
The first sample: a phone for 600,000 tenge in 24 payments of 29,990. The overpayment is 119,760, “by eye” 10 % a year. But the effective rate is 19.7 %: on average the buyer uses the shop's money for only half the term.
Newton's method works here too, but it needs care: a step from a bad point can go to a negative rate, where (1 + r)−n is huge, and for a plan with no overpayment the root is exactly at zero, where the formula divides by zero.
4+Solution
5Complexity
80 bisection steps per offer, each a couple of calls to expm1 and log1p: O(q) with a constant of about a hundred.
6Common mistakes
- Newton without an interval. From a fixed start and with division by r it breaks on plans with no overpayment; the second test has five of them in a row.
- Simple interest. (P · n − S) / S / (n/12) is almost half the honest rate in the very first sample.
- Too few steps. Bisection on [0, 1] to 10⁻⁶ in the monthly rate gives the annual rate with an error larger than allowed: the error is multiplied by 12 · (1 + r)¹¹, and by 100 when converting to percent.
- Summing the series in a loop. Correct, but with n = 360 and 80 steps it is almost 60 million operations in Python.
Algorithms behind it
bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits
2 problems
SRT
Technique
Binary search on the answer
If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving.
O(log D · cost of a check)
2 problems