You are not logged in. Please login at www.codechef.com to post your questions!

×

# explain GUESSRT from scratch

 0 someone please post the editorial(tutorial) for February 2019 challenge GUESSRT. asked 15 Feb, 14:20 0●1 accept rate: 0% You should search the FORUM. There are already many answers. here (16 Feb, 03:35) vichitr5★

 0 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$ answered 15 Feb, 23:04 42●5 accept rate: 0% Thanks man @gustavogardusi ! i appreciate your support ... this is a very nice explanation (16 Feb, 15:19)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,424

question asked: 15 Feb, 14:20

question was seen: 159 times

last updated: 16 Feb, 16:48