 # explain GUESSRT from scratch

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