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 kgrid of square unit cells. These cells must be pairwise distinct, and s and s must share a side fori i +1
i = 1 , . . . , k − 1. If the snake is currently occupying ( s , . . . , s ) and s is an unoccupied cell sharing a side
1 kwith s , the snake can move to occupy ( s, s , . . . , s ) instead.
1 1 k − 1
Initially, a snake of length 4 is in the grid { 1 , 2 , . . . , 30 } occupying the positions (1 , 1) , (1 , 2) , (1 , 3) , (1 , 4)2
with (1 , 1) as its head. The snake repeatedly makes a move uniformly at random among moves it canlegally make. Estimate N , the expected number of moves the snake makes before it has no legal movesremaining.
An estimate of E > 0 will earn b 22 min( N/E, E/N ) c points.4
解析
英文解析
- [22] A snake of length k is an animal which occupies an ordered k -tuple ( s , . . . , s ) of cells in a n × n
1 kgrid of square unit cells. These cells must be pairwise distinct, and s and s must share a side fori i +1
i = 1 , . . . , k − 1. If the snake is currently occupying ( s , . . . , s ) and s is an unoccupied cell sharing a
1 kside with s , the snake can move to occupy ( s, s , . . . , s ) instead.
1 1 k − 1
Initially, a snake of length 4 is in the grid { 1 , 2 , . . . , 30 } occupying the positions (1 , 1) , (1 , 2) , (1 , 3) , (1 , 4)2
with (1 , 1) as its head. The snake repeatedly makes a move uniformly at random among moves it canlegally make. Estimate N , the expected number of moves the snake makes before it has no legal movesremaining.
An estimate of E > 0 will earn b 22 min( N/E, E/N ) c points.4
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 36 n 2
is about n × 4 × 3 × 3 = 36 n . We can estimate the answer as = 4050, which is good enough for
13 points.8
Let’s try to compute the answer as precisely as possible. For each head position ( a, b ) and tail orientation c ∈ [0 , 36), let x = 36( na + b ) + c be an integer denoting the current state of the snake. Let Eby the expected number of moves the snake makes if it starts at state x . If from state x the snake canxtransition to any of states y , y , . . . , y , then add an equation of the form
1 2 kk
∑
E − E = 1 .1
x yii =1 k
Otherwise, if there are no transitions out of state x then set E = 0.
2 x
It suffices to solve a system of 36 n linear equations for E , E , . . . , E . Then the answer will 2
0 1 36 n − 1
equal E , where i corresponds to the state described in the problem statement. Naively, using Gaussiani
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 withinthe 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 ) realnumbers 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 exploitingsome sort of special structure:
• https://codeforces.com/contest/963/problem/E
• https://codeforces.com/gym/102501/problem/E