someone please post the editorial(tutorial) for February 2019 challenge GUESSRT.
Translating the problem:
def f(n, k, m):
if m == 0:
return 0.0
operation_1 = (1.0 / n) + ((n - 1.0) / n) * f(n + k, k, m - 1)
operation_2 = f(n % k, k, m - 1)
return max(operation_1, operation_2)
You should notice that doing the same operation twice is not the best option, so you should swap between them. I do not know how to prove it, but it is intuitive and you can use this function to check the idea.
Then, the solution is as simple as this:
start with operation 1, then operation 2, then operation 1, … until you do not have more moves.
Take care with even M, you should do operation_1 twice in the end. The solution is something like:
def f(n, k, m):
if m == 0:
return 1.0 / (n + k)
if m == 1:
return 1.0 / n
return (1.0 / n) + ((n - 1.0) / n) * f(n, k, m - 2)
This is enough for the small subtasks, as each test runs in O(M) * O(log_2(MOD)), with fast exponentiation for modular inverse.
For the large subtask, you can see this function as a geometric progression.
Let’s call (1.0 / n) as a, and ((n - 1.0) / n) as b.
If you recall the recursive function, it will be like this (for odd values) from the top:
a
ba + a
b^2a + ba + a
...
b ^ { (m / 2) } a + b ^ { (m / 2) - 1 } a + ... b ^ { 1 } a + b ^ { 0 } a
Now the answer is just the result of geometric progression.
If you did not notice it, as me :(, during the contest, I was thinking in this way:
When you need something like 111_2, you can do 2^3 - 1. It works for every base.
3^n - 1 = 3^{(n - 1)} + 3^{(n - 2)} + ... + 3^{1} + 3^{0}
Let’s go back to the formula:
b ^ { (m / 2) } a + b ^ { (m / 2) - 1 } a + ... b ^ { 1 } a + b ^ { 0 } a
Which is the same as:
a * (b ^ { (m / 2) } + b ^ { (m / 2) - 1 } + ... b ^ { 1 } + b ^ { 0 })
This can be converted to:
a * (b ^ { (m / 2) + 1 } - 1) / b