{思考之美}Tarjan算法求无向图割顶(cut vertex) v0.1

by | Leave a comment

连通的无向图G(V, E)的割顶是V中的一点，使得去掉此点后原图不连通。最简单的方法就是枚举V中的点，依次删除进行判断图是否连通，这需要 O(V * (V + E)) 的复杂度。另外就是要Tarjan算法通过一遍DFS的信息求得所有的割点。

无向图的DFS会生成一颗路径树T，并且由于是无向图，图G只能有正向边（T边）和反向边（B边），路径树中存在正向边，故两点在树中连通，则必然在原图G中连通，因此需要考虑的是如何在T删除点u后，除了正向边，原图G中的反向边是否可以将原图连通。

u为割点有以下两种情况：

  • u是T的根节点，并且有>=2个孩子节点
  • u不是T的根节点，但u的孩子节点v中，存在v为根的子树内的所有点都无法到达u的祖先。

证明：

  • u是根节点，并且有>=2个孩子节点，如果删去u则各个孩子节点为根的子树之间无法连通，并且由于是无向图G中反向边不会在子树之间存在，故无边将子树之间连通，故原图G也不连通。
  • u不是T的根节点，在树T上删除点u，则u孩子节点各个子树的点无法只通过正向边同其它点连通，因此如果u孩子节点子树的后向边里也没有指向u祖先的点，那么u孩子节点子树的点就无法到达其它点，故u为割点。反过来，如果u子节点v的子树都存在到达u祖先的边的话，则这些子树之间可以通过先到达u的祖先，然后连通。

因此我们需要记录u点到达根节点的距离level，以及其孩子节点v所在子树能到达的u的祖先节点。到达根节点的距离可以在DFS过程中求得。关键是如何求出x子树所能到达的father(x)的祖先节点。最简单的方法就是记录v子树能到达的祖先节点集合anc(v)，那么u子树能到达的祖先节点是所有孩子节点anc(v)的并集以及u能到达的祖先节点集合，然后删除不是u祖先节点的节点。这里就是Tarjan算法的精妙之处（PS：意思就是傻逼了，我也不知道robert tarjan是怎么想出来的，如果你知道的话请留言告诉我）了，上面的这个操作正好可以利用level来进行判断通过记录low(v)，表示v以及v后代中能到达的u的祖先中最接近根的点。这样就可以在DFS过程中，计算low(v) = min(后向边到达的祖先点u(u不是v的父节点), low(v的后代))。

对于u不是T根节点的情况，如果存在v使level(u) <= level(low(v))，则u为割点。

Scheme is a Pretty Language II

by | Leave a comment

I hate this, “int tmp, tmp2;”, why not “int tmp1, tmp2;” ?
Why? I do not know the future.

求得n次方根 {y^n}=x ，可以转换为求 y=\frac{x}{y^(n-1)} 的不动点，求不动点可以使用 x, f(x), f(f(x)) \ldots 不断逼近的方法，直接使用 y=\frac{x}{y^(n-1)} 求会使得抖动过大，使用平均阻尼来解决，如果一次平均阻尼无法解决，那么使用多次平均阻尼，求解 y=\frac{x}{y^(n-1)} 需要 floor(\log_2 n) 次平均阻尼。

I know what i think, but i do not know what i do!

(define (iterative-improve enough? improve)
 (lambda (guess)
   (let ((next (improve guess)))
     (if (enough? next guess)
         guess
         ((iterative-improve enough? improve) next)))))

(define (fixed-point f guess)
 (define tolerance 0.000001)
 (define (enough? v1 v2)
   (< (abs (- v1 v2)) tolerance))
 ((iterative-improve enough? f) guess))

(define (compose f g)
 (lambda (x)
   (f (g x))))

(define (repeat-func f n)
 (if (= n 0)
     (lambda (x) x)
     (compose f (repeat-func f (- n 1)))))

(define (average-damp f)
 (lambda (x)
   (average x (f x))))

(define (average a b)
 (/ (+ a b) 2))

(define (log2 x) (/ (log x) (log 2.0)))

(define (pow a n)
 (define (iter a n result)
   (cond ((= n 0) result)
         ((even? n) (iter (* a a) (/ n 2) result))
         (else (iter (* a a) (/ (- n 1) 2) (* a  result)))))
 (iter a n 1))

(define (nth-root x n)
 (fixed-point ((repeat-func average-damp
                            (floor (log2 n)))
               (lambda (y) (/ x (pow y (- n 1)))))
              1.0))

Scheme is a Pretty Language

by | Leave a comment

好久没写博文了，也不是不想写，上个月刚毕业，在要毕业的时候心情是很复杂的，最怀念的还是大学里的那些朋友，虽然以后肯定还会见面，但失去的一起在大学生活的那种快乐却永远也回不来了。

其实原来放在草稿里的时候这里还有一段，但删掉了，就像我总是把文章放进草稿里一样

最近在看SICP，这是很久之前就想看却留到现在的好多书其中一本，别的不多说了，反正我觉得fp是我目前觉得最能体现计算本质的编程范式，这本书也是一本体现计算本质的佳作（这是废话）。

由于做习题，所以需要对写出函数进行测试，手动敲总是不方便的，所以就写了下面两个函数，第一个给输入输出case进行测试，第二个给输入case和一个标准函数然后进行测试。写这两个测试函数的时候，我第一次体会真正的只关注求解问题的思考方式。

(define (test-func func test-case)
 (map (lambda (m)
        (equal? (apply func (car m)) (car (cdr m))))
      test-case))
(define (map func enum)
 (if (null? enum)
     nil
     (cons (func (car enum))
           (map func (cdr enum)))))

(define (check-func test-func sample-func test-case)
 (map (lambda (m)
        (equal? (apply test-func m)
                (apply sample-func m)))
      test-case))
(define (map func enum)
 (if (null? enum)
     nil
     (cons (func (car enum))
           (map func (cdr enum)))))

test-func使用的例子

(define (fast-expt n b a)
 (if (= n 0)
     a
     (if (even? n)
         (fast-expt (/ n 2) (* b b) a)
         (fast-expt (/ (- n 1) 2) (* b b) (* a b)))))
(define test-case '(((1 5 1) 5)
                   ((0 5 1) 1)
                   ((6 5 1) 15625)
                   ((7 5 1) 78125)
                   ((5 9 1) 59049)))
(display (test-func fast-expt test-case))

输出： (#t #t #t #t #t)

check-func使用的例子

(define (fib n)
 (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
 (if (= count 0)
     b
     (if (even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2))
         (fib-iter (+ (* b q) (* a q) (* q p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))

(define (sample-fib n)
 (sample-fib-iter 1 0 n))
(define (sample-fib-iter a b n)
 (if (= n 0)
     b
     (sample-fib-iter (+ a b) a (- n 1))))
(define test-case '((0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)))
(display (check-func fib sample-fib test-case))

输出： (#t #t #t #t #t #t #t #t #t #t #t)

前段时间想写一篇{思考之美}，主题就是“不管往回几年重来到现在都会比现在更好，也明确知道在未来也会这么想，但却不能改变这样的状况”。 现在想想，如果我是从SICP入门编程的，那现在又会是什么样子呢。

PS：在找那个想法的时候突然发现evernote里还有半篇没写完的“{思考之美}求解序列的最小循环节及此问题扩展”，我都忘记了，可又想什么时候才能写完呢？

A Problem Uses Persistent Data Structures

by | Leave a comment

这是今天凌晨Codechef April Cook-Off 2012上的题目Best Buggy Ratings，可以算是一个线段树的题目，但每次查询会用到之前某个查询结束时的状态，所以我们需要一种方法可以快速的在之前某个状态下查询结果。

先简单描述下题目，给出整数N, M, A, B, C, D和N个元素的数组V0，然后有Q个查询l, r，需要在之前某个查询后的状态下查询区间[l, r]的最大值和次大值。其中 N \leqslant 100000, Q \leqslant 100000 。每次查询后都会根据V(K - 1)数组修改为新数组V(K)为此次查询后的状态。下面这段代码描述了这个过程。

read array V0;
R1 = 0, R2 = 0;
for K = 1 to Q
    t = ( A * R1 + D ) % K
    read qi qj
    R1, R2 = top-2 Maximum ratings in range [qi..qj] in the array Vt
    Output R1 R2
    VK = Update array V(K-1) by changing V(K-1) [ ( B * R1 + D ) % N ] = ( C * R2 + D ) % M
end-for

首先，我们先思考一个常规的查询某个区间的最大和次大值，并需要修改某一个值的问题。这可以很容易的用线段树来解决，每个结点保存此区间内的最大次大值，更新的时候由于只需要修改某一个值，直接更新到叶结点就可以了，然后根据子结点的最大次大值更新结点的最大次大值。这样每次查询和修改的时间都是 O(\log N) 。
现在这个问题的难点就是，修改一个结点的值之后之前的值不能简单的去掉，所以我们需要想办法如何保存新的值。最简单的方法就是复制一颗新的线段树，然后在这颗新的线段树上进行修改，但这个问题的 Q \leqslant 100000 ，Q棵线段树不管从空间还是时间上都是灾难。所以我们要优化这个过程，注意到修改的时间是 O(\log N) 的，也就是只有 O(\log N) 个结点需要修改，我们只需要新建这 \log N 个结点就可以了，这样总共新加 Q\log N 个结点就可以了。实现的话，我们将修改原来结点的操作更改为创建新结点，由于根结点是需要修改的，所以我们保存每个新根结点的指针就可以找到每棵新建的线段树。

这个题目用到的这个结构叫做Persistent Data Structures，这个是关于这个结构很简单的问题。

搜索了一下Wikepedia上有一篇介绍Persistent data structure，在Handbook of Data Structures and Applications这本书上第31章详细的介绍了这种结构。
我还没有深入的研究这个结构，有空学习后写一篇更详细的文章。

PS：搞ACM/ICPC的童鞋可以研究下，貌似目前比赛中还不是经常出现这样的问题。

{思考之美}关于通过移位形成的置换群的置换数

by | Leave a comment

今天做了一个题目，分析后就是一个枚举后的判断，但是感觉解决的有些感性了，中间的几个结论都是观察出来了，所以细致的思考了一下。如果不清楚置换群的话，可以先看一下permutation group。有这样一个结论，通过移位形成的置换群的置换数是 \gcd(N, M) ，其中N是置换群的元素个数，M是移位的位数。例如 N=6, M=2 的置换群，如下

\begin{pmatrix}0 & 1 & 2 & 3 & 4 & 5 \\2 & 3 & 4 & 5 & 0 & 1 \end{pmatrix}

其置换数是 \gcd(6,2)=2 ，形成的置换是[2, 4, 0][3, 5, 1]。

考虑一下为什么是这样的，一个直观的入手点就是尝试几个例子，然后分析一下置换是怎样形成的，清楚了这个自然也就明白了置换数会是多少。

假设我们移位m，并且从b位置开始寻找置换，那么置换将会是 (mX+b)\bmod n (X是自然数)得到的数字。例如 N=9, M=6 时,有如下的置换群

\begin{pmatrix}0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5\end{pmatrix}


从 b=0 位置开始， [6*1\bmod 9 = 6, 6 * 2 \bmod 9 = 3, 6 * 3 \bmod 9 = 0]

从 b=1 位置开始， [(6 * 1 + 1) \bmod 9 = 7, (6 * 2 + 1) \bmod 9 = 4, (6 * 3 + 1) \bmod 9 = 1]

从 b=2 位置开始， [(6 * 1 + 2) \bmod 9 = 8, (6 * 2 + 2) \bmod 9 = 5, (6 * 3 + 2) \bmod 9 = 2]

对于这个例子观察发现，形成的置换貌似就是模 \gcd(N, M) 的同余类。看看这是不是正确的，前面的分析过程使我们将置换转换为 (mX + b) \bmod n 这样的一个式子， 也就是说这个式子的结果根据b的不同为什么会形成模 \gcd(m, n) 的同余类。经过试错的思考，我得出了下面的分析，在这里 b < n ， (mX + b) \bmod n = mX \bmod n + b ，这样我们可以只分析 mX \bmod n 这一部分，如果我们的推断是正确的话，当 X = \gcd(m, n) 时， mX \equiv m * 0 \pmod n ，也就是 \gcd(m, n) * m | n ，根据算数基本定理，可以得出下面的推导，这里我写了几个例子，我总感觉例子会比字母的通式更容易的帮助我们观察。首先我想到 m = { {p_1}^{a_1}} * { {p_2} ^ {a_2}} * \ldots * { {p_n }^{a_n} } ， n = { {p_1}^{b_1}} * { {p_2}^{b_2}} * \ldots * { {p_n}^{b_n}} ，则 \gcd(m, n) = { {p_1} ^ {\min(a_1, b_1)}} * { {p_2} ^ {\min(a_2, b_2)}} * \ldots * { {p_n} ^ {\min(a_n, b_n)}} ，列出来之后，带入式子发现，前面的观察可能不正确，因为带入后得到的每一个项是 {p_1} ^ {((a_1 - b_1) + \min(a_1, b_1))} ，这并不能保证是整数，也就是不能保证 \gcd(n, m) * m | n 是正确的。这时我又尝试了9 15这个例子后，意识到了其实前面的结论是正确的，但我错在了第一个加黑处的推导，其实正确的应该是由于置换数是 \gcd(n, m) ，所以每个置换有 \frac{n}{\gcd(n, m)} 个元素，所以当 X = \frac{n}{\gcd(n, m)} 时, mX \bmod n = 0 ，这样就很显然了。这个分析其实是很简单的，但分析思路并没有很严谨，所以出了错误，在中间分析的时候，最大的错误是忘记了其实这个是证明题，是已经知道结论的，但前面那个加黑的“貌似”如果不正确的话，那么前面的置换数的结论也就不正确了。

### Update:

又发现了一个漏洞，上面的推导只说明了 (mX + b) \bmod n 这个式子存在 n \bmod \gcd(n, m) 长度的循环周期，但并没有说明是否存在小于此的循环周期。所以我想将下面的说明加入推导会更严谨一些，我们知道 mX \equiv mY \pmod n -> (m(Y - X)) \equiv 0 \pmod n ，当X = 0时， mY \bmod n = 0 ，也就是要证明满足此式子的 Y > 0 的最小值是 \frac{n}{\gcd(n, m)} ，我们假设 b < \frac{n}{\gcd(n, m)} 时， mb | n ，显然 mb | m ，那么mb就是n和m的最小公倍数，但是 b * m < n * \frac{m}{\gcd(n, m)} 的，右边才是最小公倍数，所以是矛盾的。（这个证明关键就是联想到最小公倍数，我是这么想到的将 X = \frac{n}{\gcd(n, m)} 带入式子后会出现最小公倍数，那么我们取 X < \frac{n}{\gcd(n, m)} 也就是小于最小公倍数的值，这正好可能会产生矛盾，所以有了上面的证明）

{思考之美}寻找匈牙利算法的贪心优化无法保证字典序匹配的原因

by | Leave a comment

今天搞了一个题目，在建立起二分图模型之后，需要进行最大匹配，并且要保证能够匹配的左边X集的点的下标是字典序最小的，这样使用匈牙利算法可以很容易的解决这个问题，只要我们按照X集的点下标从小到大的顺序寻找增广路就可以了。这很容易证明，由于一个图的最大匹配数是一定的，并且匈牙利算法是 x_1 \ldots x_n 依次判断点是否可以构成匹配的，点 x_i 只能在判断它时才可能构成匹配，并且这不会影响 x_j(i \neq j) 的匹配状态，所以我们按照下标从小到大顺序判断，让试图在 x_1 \ldots x_{i-1} 匹配状态下，让最小下标的点先匹配，归纳下来，最终的结果的字典序就是最小的，如果要字典序最大的话，下标从大到小排序就可以了。

题目规模比较大，匈牙利算法超时，所以我想先优化一下。贪心优化其实很简单，效果的话不明显。其主要就是在建图的时候，把能够匹配的先进行匹配，之后判断的时候已经有匹配的点了，所以会快一点。加上这个优化后，wrong了。那么错误点可能有两个，不能产生最大匹配，不能保证字典序。首先看一下是不是能够保证最大匹配，图中没有增广路就是最大匹配，存在增广路才会有更大的匹配，判断增广路时，我们从开始点是左侧未匹配的点开始，考虑其判断以后，如果其匹配那么这个点就不会再是增广路的端点了，这个过程是不会受到目前匹配情况影响的，只要依次判断左侧未匹配点就可以了，所以依然会产生最大匹配。

然后是保证字典序，开始的我一直认为是可以的，因为陷进了优化时匹配也是下标从小到大进行的误区，感觉也应该是字典序的，但这忽略了为什么匈牙利算法可以是字典序的最重要的原因---如果在保证 x_1 \ldots x_{i-1} 的匹配情况下判断 x_i 不能匹配，那么 x_i 在这种状态下就不可能匹配---但是优化的时候没有这个性质， x_i 不能匹配，并不是在 x_1 \ldots x_{i-1} 匹配情况不变的时候肯定不能匹配（因为没有寻找增广路），但是我们由于在 x_i 之后的点中找到了匹配的点(最大匹配数一定，这就减少了 x_i 匹配的可能)，所以造成了最后增广路判断的时候找不到 x_i 的匹配。为了直观认识这一点，我们寻找一个例子，分析给了我们方向，所以我们需要构造一个实际可以匹配1,2，但因为1,3得到匹配，而2无法匹配的情况。我们需要让2在优化判断时的匹配点让1占据，然后让3找到匹配点，(1, 1), (2, 1), (3, 2)然后使得3不匹配时，为使2增广时可以匹配，加入(1,2)边，然后我们得到了样例。看来仔细分析之后对找出样例是很有帮助的。

PS:记录下思考过程，推荐刘未鹏的一篇文章书写是为了更好的思考。