HackerRank Probability – The White Lotus and Caterpillar game

Challenge: The White Lotus and Caterpillar game

Subdomeniu: Probability (probability)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464753305

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/the-white-lotus-and-caterpillar-game/problem

Cerinta

As usual Gary and Flo are sitting at their favourite burger restaurant called *Jim's Burgers*. They want to treat themselves with delicious burger after an interesting day with lots of competitive programming. So they have ordered their burgers and are waiting for them. But with nothing to do, they get bored and decide to play a game.

The game is played on a sheet of paper with $n$ rows and $m$ columns and goes as follows: 

Flo places his white lotus tile somewhere at the top row and Gary places a caterpillar tile somewhere on the bottom row. Flo begins the game and their turns alternate. Flo can move his tile to any of the 8 adjacent cells, while Gary's caterpillar tile can only move  __left__ or __right__, or __stay__ at the same cell. Of course, they cannot step outside of the grid. Flo's goal is to catch Gary as fast as possible, that is, with the minimum number of moves, while Gary (with the caterpillar tile) has to survive for as long as possible.  

Now they are wondering: If they place their tiles in the corresponding rows and some random columns, what is the expected number of moves Flo has to make to win the game (assuming they will play optimally)? 

Can you help them answer this question?

**Constraints**

$ 2 \leq n,m \leq 5000 $

**Input Format**

You will be given two space separated integers $n$ and $m$, denoting the number of rows and the number of columns on the board respectively. 

**Output Format**

Output the answer in one line. 

**Note**: The answer will be considered valid if it differs from the correct answer by at most $10^{-6}$.

**Sample input**

	2 3
**Sample output**

	1.2222222

Consider the pair $(x, y)$ as the starting column of the lotus and the starting column of the caterpillar respectively. 

For $n = 2$ and $m = 3$ we get the following scenario. 

$(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3)$ will lead to 1 move. 
The remaining pairs $(1, 3)$ and $(3, 1)$ will lead to 2 moves. So the expected value  is $\frac{1+1+1+1+1+1+1+2+2}{9}=1.222..$

Cod sursa

#!/bin/python3

import sys


def expected_moves(n: int, m: int) -> float:
    d = n - 1  # Minimum moves needed for lotus to reach bottom row.

    total = 0
    for x in range(m):
        # y = x (same column) and adjacent columns always cost exactly d (d >= 1).
        adj = (1 if x > 0 else 0) + (1 if x < m - 1 else 0)

        # If caterpillar starts at least two cells to the left, optimal survival is x moves on bottom-row chase.
        # If at least two cells to the right, optimal survival is (m-1-x) moves.
        left_survival = max(d, x)
        right_survival = max(d, m - 1 - x)

        left_count = max(0, x - 1)
        right_count = max(0, m - x - 2)

        total += d * (1 + adj) + left_count * left_survival + right_count * right_survival

    return total / (m * m)


def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])

    ans = expected_moves(n, m)
    print(f"{ans:.10f}")


if __name__ == '__main__':
    main()