samay_var's blog

By samay_var, history, 4 years ago, In English

Here is the link to the question at CodeDrills:

There is a knight(chess piece) at every square of the N * N chess board and in each step each knight moves uniformly randomly to each square it can move within the board. Multiple knights are allowed on each square. Calculate expected number of empty squares after K steps. Find the value upto 6 digits of precision after the decimal point.

Note :- Knight movement in chess

Input Format Single line containing two space seperated integers N and K.

Output Format The required value upto 6 digits of precision after decimal point. The answer will be considered correct if the absolute difference between your answer and judge answer is within 10^-6

Constraints 4 <= N <= 20 1 <= K <= 10^6

Sample Input 0 4 1

Sample Output 0 5.361111111111111

Sample Explanation Expected value of number of empty squares after one step is equal to sum of probabilities of each square to be empty in one step.

Let's define P(x, y, u, v) as prob that a knight in square (x,y) doesn't move to square (u, v).

For example let's consider the square (1,1)

The probability for this square to be empty in one step = P(2, 3, 1, 1) * P(3, 2, 1, 1)

P(2, 3, 1, 1) = 3/4 (Because there are 4 possible moves for a knight at square (2, 3) and there is only one knight at (2, 3) initially)

Similarly P(3, 2, 1, 1) = 3/4

If we compute the probabilities for all the squares in a similar manner and sum them we get the above answer.

Help me in solving this problem...

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I believe you can model the chessboard as a graph with $$$n*n$$$ nodes, where edges connect the squares according to the Knight moves.

Now, create the adjacency matrix for the graph with values as the probability of corresponding transitions, and get the final probabilities of a particular square being occupied after $$$k$$$ moves (using matrix exponentiation).

The answer is just the summation of probabilities of each square to be empty after $$$k$$$ steps.

PS: The matrix can be reduced to $$$1/4th$$$ of its original size, to optimize the solution.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem is similar to this https://cses.fi/problemset/task/1726