Codeforces Round #572 (Div. 1) C. Array Beauty

题意

我们称一个序列\(\{b_i\}_{i=1}^k\)的beauty值为\(\min_{i \neq j} |b_i – b_j|\)。 给定序列\(\{a_i\}_{i=1}^n\),问所有长度为k的子序列的beauty值之和。

数据范围:\(2 \leq k \leq n \leq 1000, 0 \leq a_i \leq 10^5\)

题解

我们可以使用一个常见的技巧:令\(P(t)\)为所有beauty值大于等于t的长度为k的子序列个数,那么答案就是\( \sum_{t=1}^{\infty} P(t) \)。

这样问题就变成了计数题。首先将输入序列排序,令\( p_t(i) = \max\{j : a_j – a_i \geq t\} \),那么转移就可以写成:\( f_t(i, j) = f_t(i, j-1) + f_t(i-1, p_t(j)) \),且\(P(t)= f_t(k, n)\)。可以在均摊\(O(n^2)\)时间内求出所有 \(p_t(i)\)的值,另外计算一个P(t)的值需要\(O(nk)\)时间。注意到P(t)是单调递减的,因此当出现P(t)=0时就不必继续计算了。这样的t不会超过\(\frac{\max a}{k-1}\),因此总的复杂度为\(O(n \max a)\)。

Counting independent sets in O(1.619^n) time

Given a graph \(G=(V, E)\), an independent set \(I\) of \(G\) is a subset of \(V\), such that every two vertices in \(I\) are not adjacent. We give an algorithm to count the number of independent sets of a given graph on \(n\) vertices. The main idea of the algorithm is divide and conquer.

Counting independent sets of \(G\): CIS(G)

  1. If \(G\) contains multiple connected components, count the independent sets of each component and multiply the numbers.
  2. If \(G\) contains only one vertex, return 1.
  3. Otherwise, arbitrarily select a vertex \(v\). Remove \(v\) and count the number of independent sets of the remaining graph. Remove \(v\) and its neighbors and count the number of independent sets of the remaining graph. Return the sum of two.

To see the O(1.619^n) running time, note that in step 3, removing \(v\) decreases the number of vertices by one, while removing \(v\) and its neighbors decreases the number of vertices by at least two. The recurrent is identical to Fibonacci sequence.

Solving Sparse Linear System in O(nm) Time

There are many practical applications that involve solving sparse linear system \( \mathbf{A}\mathbf {x} = \mathbf{b} \), such as random walk in sparse graphs. Traditional techniques such as Gauss elimination or LU decomposition applies for general linear systems, and they run in cubic time. Fastest known algorithms for general matrix run in about \( O(n^{2.373}) \) time. However, for sparse matrix, we may achieve a much faster result. Specifically, we may solve the system in \(O(mn)\) time, where \(m\) is the number of nonempty entries in \(\mathbf{A}\).  We assume that the matrix \( \mathbf{A} \) is non-singular (i.e., invertible) throughout this passage.

1. Inverting a matrix from its annealing polynomial

Given polynomial \( p(x) \), if \( p(\mathbf{A}) = \mathbf{0} \) for matrix \( \mathbf{A} \), then we say \(p(x)\) is an annealing polynomial for matrix \( \mathbf{A} \). Due to Hamilton-Cayley theorem, the characteristic polynomial \(\det( x\mathbf{I} – \mathbf{A} ) \) is an annealing polynomial for \( \mathbf{A} \). Among all annealing polynomials for matrix \( \mathbf{A} \), the one with minimum degree is called the minimal polynomial for \( \mathbf{A} \). It can be proved that the minimum polynomial for given matrix is unique up to a constant factor, and any other annealing polynomial is a polynomial multiple of the minimum polynomial.

We can invert a matrix \( \mathbf{A} \) if we have a minimal polynomial for \( \mathbf{A} \) :
\[ a_0 I + a_1  \mathbf{A} + a_2 \mathbf{A}^2 + \cdots + a_k \mathbf{A}^k = 0 \tag{*} \]Since \( \mathbf{A} \) is invertible, 0 is never a root of its characteristic polynomial, hence we must have \(a_0 \neq 0 \). Multiplying \( \mathbf{A}^{-1} \) on both sides yields
\[ \mathbf{A}^{-1} = -\frac{a_1 I + a_2 \mathbf{A} + a_3 \mathbf{A}^2 + \cdots + a_k \mathbf{A}^{k-1}}{a_0} \]this means that we may represent the inversion of \( \mathbf{A} \) by the linear combination of powers of  \( \mathbf{A} \).

2. The Berlekamp-Massey algorithm

Berlek-Massey algorithm solves the following problem in $O(n^2)$ time:

Given a finite sequence \(\{x_i\}_{i=1}^n\), find a minimum order linear recurrence consistent with the given sequence. Formally, find a shortest sequence \(c_0 = 1, c_1, \cdots, c_{k-1}\), such that \(\sum_{l=0}^{k-1} x_{j-l} c_l = 0\) holds for all possible \(j\).

 This algorithm has many real world applications. The most typical one is to find the shortest linear feedback shift register for a given binary sequence. Also, it can be viewed as interpolating a sequence with exponential terms. One important fact for Berlekamp-Massey algorithm is, for an order-\(r\) linearly recurrent sequence, taking the first \(2r\) elements as the input of the algorithm suffices to recover the recurrence.

3. Finding the minimum polynomial 

Note that the annealing polynomial is exactly the linear recurrence of powers of a matrix. However, it is infeasible to compute the minimum polynomial from the powers of \(\mathbf{A}\). However, we may randomly pick vectors \(\mathbf{u}\) and \(\mathbf{v}\) and compute the minimum polynomial from \(\mathbf{u}^T \mathbf{A}^i \mathbf{v}\). We claim without proof that, with high probability, the coefficients of the recurrence of the sequence are exactly those of the minimum polynomial. The sequence can be computed in \(O(mn)\) time by iteratively doing sparse matrix-vector multiplication in $O(m)$ time. Finally, apply Berlekamp-Massey algorithm to the given sequence.

4. Solving the linear system

Since the inverse of a sparse matrix is generally not sparse, we won’t actually compute the inverse of \(\mathbf{A}\).  Actually, we can compute \(\mathbf{A}^{-1}\mathbf{b}\) via formula (*) in \(O(mn)\) time. The procedure is exactly the same as in finding minimum polynomial: just iteratively perform spare matrix-vector multiplication.

Nordic Collegiate Programming Contest 2018 [NCPC2018] 题解

A. Altruistic Amphibians

unsolved

B. Baby Bites

solved (0:08, +1)

逐个检查即可。

C. Code Cleanups

solved (0:17)

逐日模拟即可。

D. Delivery Delays

solved (4:55)

首先跑最短路获取APSP。

二分答案,然后dp出送完前i单最早时间,或者不可行

E. Explosion Exploit

solved (3:23)

可以用dp的思想转移。由于随从的顺序无关,可以将他们的血量排序,总状态数会大大减少。

F. Firing the Phaser

unsolved

G. Game Scheduling

unsolved

H. House Lawn

solved (0:34)

如果\(\frac{10080rc}{t+r} \geq l\),则说明可行。记录可行的机器中,最便宜的那些机器的名称即可。

I. House Lawn

solved (1:00 +1)

由于相邻两数相差至少为一倍,只需要从大到小排序,然后能减就减。最后结果为0,则选中的那些就是答案。

J. Jumbled String

solved (1:57 +2)

可以根据00和11子序列的数量算出0和1的数量,然后根据01和10子序列的数量调整0和1的位置。注意若干边界情况。

K. King’s Colors

solved (3:07)

用最多k种颜色染色有\((k-1)^{n-1}k\)种方案。用恰好$k$种颜色的方案数可以用容斥算出。