HMMT 二月 2020 · 冲刺赛 · 第 36 题
HMMT February 2020 — Guts Round — Problem 36
题目详情
- [22] A snake of length k is an animal which occupies an ordered k -tuple ( s , . . . , s ) of cells in a n × n 1 k grid of square unit cells. These cells must be pairwise distinct, and s and s must share a side for i i +1 i = 1 , . . . , k − 1. If the snake is currently occupying ( s , . . . , s ) and s is an unoccupied cell sharing a side 1 k with s , the snake can move to occupy ( s, s , . . . , s ) instead. 1 1 k − 1 2 Initially, a snake of length 4 is in the grid { 1 , 2 , . . . , 30 } occupying the positions (1 , 1) , (1 , 2) , (1 , 3) , (1 , 4) with (1 , 1) as its head. The snake repeatedly makes a move uniformly at random among moves it can legally make. Estimate N , the expected number of moves the snake makes before it has no legal moves remaining. 4 An estimate of E > 0 will earn b 22 min( N/E, E/N ) c points.
解析
- [22] A snake of length k is an animal which occupies an ordered k -tuple ( s , . . . , s ) of cells in a n × n 1 k grid of square unit cells. These cells must be pairwise distinct, and s and s must share a side for i i +1 i = 1 , . . . , k − 1. If the snake is currently occupying ( s , . . . , s ) and s is an unoccupied cell sharing a 1 k side with s , the snake can move to occupy ( s, s , . . . , s ) instead. 1 1 k − 1 2 Initially, a snake of length 4 is in the grid { 1 , 2 , . . . , 30 } occupying the positions (1 , 1) , (1 , 2) , (1 , 3) , (1 , 4) with (1 , 1) as its head. The snake repeatedly makes a move uniformly at random among moves it can legally make. Estimate N , the expected number of moves the snake makes before it has no legal moves remaining. 4 An estimate of E > 0 will earn b 22 min( N/E, E/N ) c points. Proposed by: Andrew Gu Answer: ≈ 4571 . 8706930 Solution: Let n = 30. The snake can get stuck in only 8 positions, while the total number of positions 2 2 2 36 n is about n × 4 × 3 × 3 = 36 n . We can estimate the answer as = 4050, which is good enough for 8 13 points. Let’s try to compute the answer as precisely as possible. For each head position ( a, b ) and tail orien- tation c ∈ [0 , 36), let x = 36( na + b ) + c be an integer denoting the current state of the snake. Let E x by the expected number of moves the snake makes if it starts at state x . If from state x the snake can transition to any of states y , y , . . . , y , then add an equation of the form 1 2 k k ∑ 1 E − E = 1 . x y i k i =1 Otherwise, if there are no transitions out of state x then set E = 0. x 2 2 It suffices to solve a system of 36 n linear equations for E , E , . . . , E . Then the answer will 0 1 36 n − 1 equal E , where i corresponds to the state described in the problem statement. Naively, using Gaussian i 2 3 13 elimination would require about (36 n ) ≈ 3 . 4 · 10 operations, which is too slow. Also, it will require 2 2 too much memory to store (36 n ) real numbers at once. We can use the observation that initially, the maximum difference between any two indices within the same equation is at most ≈ 72 n , so Gaussian elimination only needs to perform approximately 2 2 11 2 (36 n ) · (72 n ) ≈ 1 . 5 · 10 operations. Furthermore, we’ll only need to store ≈ (36 n ) · (72 n ) real numbers at a time. Benjamin Qi’s solution ends up finishing in less than two minutes for n = 30 (C++ code). Here are some more examples of problems in which Gaussian elimination can be sped up by exploiting some sort of special structure: • https://codeforces.com/contest/963/problem/E • https://codeforces.com/gym/102501/problem/E