问题描述

电影院有N排坐椅，每排坐椅有N个坐位，这样整个电影院就有\( N^2 \)个座位，每排都按相同方向从左向右计序号，第1排从左到右序号分别是1,2,3,…N,第2排从左到右分别为N+1,N+2,…,2N,最后一排分别是\(N^2-N+1,N^2-N+2,…,N^2 \)。

这一场电影坐无虚席。散场时所有观众将会按照序列\( \{P_i\} \)的顺序离场，但是如果 \(x \)离场的时候，与他的坐位相邻上下左右四个方向都还有其它观众没离场，那么\( x \)的离场就需要强行越过这个人出去，那么就会招致这个观众\(y \)对\( x \) 的不满，将这一组不满意记录记为\( (x,y) \)。此问题给出电影院的规模N和离场顺序，计算这个离场顺序最少有多少不满意记录。

agc044_b

分析

For each \( 1 \leq i \leq N^2 \) , we compute the minimum number of viewers that will hate viewer \(i\) forever (the answer is the sum of these values). This number coincides with the minimum cost of a path from the seat of viewer \(i\) to the sides of the square, considering that going through an empty seat has cost 0 and going through an occupied seat has cost 1. Let \( H_k(i) \) be the minimum cost (as defined above) of a path from the seat of viewer i to the outside after the first \(k\) viewers have left the cinema.

Key observation
The values \( H_k(i) \) are decreasing (for \( k \) going from \( 0\) to \( N^2 \) ) and at the beginning we have
\[ \sum_{k=1}^{N^2}{H_0(k)} \approx \frac{N^3}{6} \]

Our strategy is to keep all values \( H_k(i) \) updated at all times. Initializing \( H_0(1), … , H_0(N^2 ) \) in \(O(N^2) \) is straightforward. Let us show how to update \( H_{k−1}(1), … , H_{k−1}(N^2 ) \) to get \( H_k(1), … , H_k(N^2 ) \). When the viewer \(P_k\) goes away, we perform a breadth-first search (or a depth-first search) starting from the seats of \( P_k \) and updating the values. During the k-th breadth-first search, we will visit only the seats \( i\) such that \( H_k(i) < H_{k−1}(i) \), hence the total number of seats visited in the \( N^2\) steps (for \( 1 \leq k \leq N^2 ) \) is \( O(N^3 ) \) (see the key observation).

The time complexity of this solution is \( O(N^3 ) \) with a small constant which is sufficient to get accepted (some optimization might be required in slow languages such as python).