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

×

explain GUESSRT from scratch

someone please post the editorial(tutorial) for February 2019 challenge GUESSRT.

asked 15 Feb, 14:20

wingman__7's gravatar image

3★wingman__7
01
accept rate: 0%

You should search the FORUM. There are already many answers. here

(16 Feb, 03:35) vichitr5★

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$

link

answered 15 Feb, 23:04

gustavogardusi's gravatar image

5★gustavogardusi
425
accept rate: 0%

edited 16 Feb, 16:48

Thanks man @gustavogardusi ! i appreciate your support ... this is a very nice explanation

(16 Feb, 15:19) wingman__73★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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