Monthly Archives: July 2009

联合训练赛第二场解题报告

A. The Troubles of Lmy

多边形相似,实际上是一个字符串匹配,利用相邻两边的比例和该顶点的角度作为一个节点,如果两个多边形相似,那么这样的n节点肯定是能够循环匹配的。注意不能光用角度来匹配,正方形和长方形就是一个反例。也不能用相邻边的比例来匹配。如菱形和正方形。

B. The Evaluation of Determinant

若m为素数,即可以用O(n^3)的高斯消元来解(与实数域的高斯消元类似,把除法变为乘以逆元即可,当m为素数时易知这样的逆元一定存在)。对于此题,需要把m拆成素数的积,对每个素因子求出一个结果,再利用中国剩余定理解模方程组,从而得到最终结果。

C. Lamp

此题实际上是一个特殊的SAT问题,每个开关对应一个变量,每个灯泡对应一个子式。关键条件是每个开关最多控制两个灯泡(注意这不是2-SAT问题)。我们可以通过一个构造的方法解决此题:首先,对于不控制任何灯泡的开关,它是任意状态都可以。然后,对于只控制一个灯泡的开关,或者控制两个灯泡但同亮同灭的开关,可以很容易地决定此开关的状态,只需令它控制的那一个或两个灯泡k(以及k’)亮着就可以了,然后灯泡k(以及k’)对应的子式就可以忽视掉了,这样就可能得到更多的只控制一个灯泡的开关。持续此过程,直到所有的灯泡都亮了,或者找不到满足上面情况的开关。在后面一种情况下,剩下的开关全部控制两个灯泡,并且若开关为ON时点亮其中一个灯泡,为OFF时点亮另一个。此时我们可以建立一个二分图,把剩下的灯泡作为X集,把开关作为Y集,若某灯泡被某开关控制,则在两者之间连边,求此图的最大匹配,若所有的灯泡都能被匹配上,则解存在,开关的状态就是满足使其对应的灯泡点亮的那个状态。

D. Lawrence of Arabia

这个去年North America的区域赛题目,dp模型很简单,dp[i][j]表示对前i段railroad进行j次attack所需要的最小值,那么转移方程为
dp[i][j]=min{dp[k][j-1]+weight(k+1,i):j<=k<=i-1}
对于固定的j,可以看出dp[i][j]的决策是随着i单调不减的,建立数组len[x]表示使决策x比之前所有的决策(y<x)都要好的最小的位置i。可以通过二分求出这个最小位置同时用栈维护所有的有效决策序列,这样对于每一维固定的j,复杂度可以降到nlogn,所以最后总的复杂度可以达到n^2logn。

E. Matrix Swapping II

对每个位置,计算出从它自身向下共有多少个连续的1,设此数为c[i][j]。这一步可以用O(n^2)解决。然后枚举每一行i,假设它是要找的子矩阵的最上一行,取出此行的所有c[i][j],容易发现只要把这些值排序后,即可用一遍扫描得出以i行为最上一行的全1子矩阵的最大面积。所以总的复杂度是O(NMlogM)。另外如果仔细考虑上一行和下一行之间c值的转换关系(-1或者赋一个新值),可以得到O(NM)的算法。

F. Plants VS Zombies

贪心,对于每个僵尸,求出要杀死它所需的最少种花时间x[j] = V[j] – ceil(D[j] / T) * T,将其时间从小到大排序,依次杀死即可。如果到某位置时时间不够,则无解。

G. Snail’s trouble

简单题。蜗牛每分钟走的距离占总长度的比例依次为 (k/100)/1, (k/100)/2, (k/100)/3, … 因为调和级数1+1/2+1/3+…+1/n不收敛,故蜗牛总能爬到终点。对于此题,精度要求不高,直接暴力或打表即可通过。也可以用Striling近似公式来解。

H. Wukong and Tang Monk

首先求出A和C到图中所有点的最短路径,然后分别从B和D倒推求出WuKong和Tangseng可能经过的结点(如果dist[i]==dist[j]+w(i,j),i在最短路中,那么j也必在一条最短路)。那么通过这些结点和最短路的边就可以得到两个有向无环图,问题就变为分别在这两个有向无环图中找出A到B的一条路径和C到D的一条路径,使其公共顶点最多。可以采用类似最长公共子序列的dp思想自下至上dp,dp[i][j]表示wukong沿着某条最短路径到达i结点,tangseng沿着某条最短路径到达j结点时的最多公共顶点数,那么通过枚举i和j的前驱结点,则有
if(i == j)dp[i][j]=1+max{dp[pre[i]][pre[j]]};
else dp[i][j]=max{dp[pre[i]][j],dp[i][pre[j]]};

I. Girl Friend II

此题实际上是在语音识别、机器学习等领域被广泛应用的所谓的隐马尔科夫模型(HMM),解决此问题的算法被称为Viterbi算法,实际上就是一个简单的DP。我们用dp[i][j]表示在第i分钟,女孩的状态为j时的似然概率,则有状态转移方程

dp[i][j] = max{dp[i-1][k] * p[k][j] * a[j][b[i]], for all state k}

边界条件 dp[0][j] = s[j] * a[j][b[0]]

这里p,a,b,s的含义和题目中一致。可以把所有概率取log后,变乘法为加法,这样可以避免最后得到过分接近零的小数。算法的复杂度为O(T*N*N)

//继续无责任废话

这次C,E,F,I是我出的。C题来自计算理论课本上的一道课后题(我还是很对得起老廖这课的),貌似有队伍的解法比我的更为简洁,大意也是二分匹配,但没有很多的预处理;E是从前几天刚结束的CEOI 2009抄的,囧,数据放宽了不少;F和I其实都是临时凑数想的,当时觉得这一场比上一场要难,根据前一场大家的表现,拿掉了本来的一道难题,换了这两个简单题,F题背景是最近很火的“植物大战僵尸”,本来想的是匹配,后来发现水了,贪心就可以过-_-;I题其实就是随便yy了一下HMM,结果发现挺不好描述的,所以弄了很长的题面,相信不少队伍是被超长的题面和里面的公式吓得不敢想了,其实真的不难,不过事前真没想到精度会导致这么大的问题,我当时随手用两种稍微不同的方法写了两个程序(一种是/100后连乘,一种是直接log相加),得到的结果非常接近,以为问题不大。后来交上的程序一开始全是WA,一度让我以为是我的数据错了,但是用程序算过以后发现他们的程序的概率确实都小于我的标准输出,后来TJU-T03终于把这个过了我才放了心。

联合训练赛第一场解题报告

A. A Sequence of Numbers

简单题。求等比数列的时候应该用二分法求幂。注意处理好64位整数的操作不要溢出。

B. Building Block

并查集,每个元素存了两个数。其中一个只在代表元上有效,存了这一堆积木的总个数;另一个数的作用是,对于每个元素,从它到代表元的路径上这些数的和,是在这个积木上方的积木的个数(不包括它自己)。

C. Matrix Swap

建立一个N*N的二分图,若第i行第j列为1,则在X集的第i个点与Y集的第j个点之间连边,若此图的最大匹配数小于N则无解。否则,我们就可以由匹配的情况得到一个交换方案,例如我们可以把与X集的每个点所匹配的Y集中的点编号列出,这样得到一个1..N的排列,然后可以通过交换序列中的数(即交换原矩阵的列)得到一个1,2,3…N的递增序列。最后这步实际就是找这个置换中的循环。

D. Permutation

状态压缩DP.我们考虑把数字从小到大依次插入序列之中某个位置的过程,有一个重要的观察是,若当前考虑插入的值是a,则现在序列中小于a-K的值就可以完全不予考虑,因为新的值不可能插入与这种值相邻的位置,例如K=3, 现在已经形成的序列是{4,1,2,5,6,3},目前要插入的元素是7,则可以发现7只能放在最左端或插入5,6之间,而1,2,3这几个值都可以不予考虑,故上述序列可以简化表示为{4,*,5,6,*},其中*表示不能在其邻位插入当前值的一个元素或连续一段元素.这样总的序列长度不超过2*K+1,每个位置的取值只有K+1种,所以状态总数不超过(K+1)^(2K+1),更精细的分析可以得到更小的结果.另外,此题实际上只要有一个复杂度相对可行的算法,能够在比赛时间内把表打出来即可,而用上面这种状态表示得到的DP已经足够满足要求。

E. Pusher boys

搜索题。标程的实现方法是DFS + Hash判重。数据没有出得很大,不需特殊的剪枝即可通过。另外,在题目给出的网站上提供了用程序自动获取迷宫数据的办法 http://www.hacker.org/forum/viewtopic.php?t=528 ,各关的难度是递增的,本题的数据取自最容易的若干关,感兴趣的同学可以用自己的程序看看能解出多少。

F. Prairie dogs V

BFS。当扩展到一个’X’点时把与其相连的所有X都入队即可。

G. The Wildest Road

其实就是求两个凸包的最短距离,要考虑只有一个点和所有点都在一条线上的情况。最短距离可以通过枚举顶点到另外一个多边形上的所有边的距离,同时加上相交判断和点再多边形内部的判断。注意考虑一个多边形完全包含另一个的情况,以及虽然两多边形相交但没有任何一个顶点在另一多边形内的情况。

H. Euler Function

设n的素因子分解为n = p1^k1 * p2^k2 * … * pm^km,则phi(n) = n * (1 – 1/p1) * (1 – 1/p2) … * (1 – 1/pm).利用此式可以用一个类似筛法求出所有的phi,再累加求和即可.

I. Wireless Network

在字符串自动机上进行状态压缩DP。首先以所有的密码串建立自动机,注意在自动机的终止结点上标记出其能匹配上哪些密码。设DP的状态为dp[len][pos][mask],表示当前长度为len的串,处于自动机编号为pos的结点处,之前已经匹配上的密码集合位串为mask。每次枚举下个字符的26种可能进行状态转移。边界条件为dp[0][0][0] = 1,最后结果为sum{dp[n][pos][mk]},这里pos取遍所有结点,mk取遍所有包含不少于k个1的位串,求总和即可。时限略紧,算法实现时要注意一下常数。

//以下为无责任废话

这九道题对应题目为TOJ 3293 –TOJ 3301,其中C,D,E三题是我出的。

C题是翻Algorithms Design那书的课后题时看到的,在已经知道那是讲网络流的那章的课后题的情况下,当时我居然愣了好一会儿才想到怎么做。想来这么经典的模型应该是早有人出过了,所以加了一个输出解的SPJ,算是加难了一点,本来想弄成要求交换次数最少,但是那样的话我觉得无法确定用匹配找到的就是最优解,所以作罢,各位如果有什么想法可以与我讨论。

D是从一个搞TCS的大牛的Blog(blogspot被盾,请设法翻墙)上看到的,据说是以前罗马尼亚国内OI比赛的一题,原题的范围更大,K好像到了十几,我上面说的DP方法应该过不了,不清楚还有什么更好的办法。这场比赛里AC了此题的TJU-T06所用的方法也与我的类似。

E是前几天从水木算法版看到的一个帖子得来的,数据取自此游戏的前三十关左右,我的几乎裸搜的程序能搜到60关左右,再后面的就搞不定了,也暂时没想到很好的剪枝手段或估价手段,网站上有人搞到了300多关,实在是orz。当然对于这道题来说,是只要敢写就可以过的,就看比赛中哪队能匀出时间来试一下了。

PAC Learning

PAC的全称是Probably Approximately Correct,首先是一些符号的定义,下面以图像中的字符识别为例说明:

X: 所有可能实例的集合,如n维的0/1位图矩阵{0,1}^n,其中一个具体值表示为x
c: concept,是指一个X的子集,或者说是一个X中的元素到布尔值的{0,1}映射,比如“该字符是8”这个concept就表明一个映射,它对所有是8的图像x有c(x)=1,对于其它x有c(x)=0
C: 一系列concept的集合
D: X的概率分布
h: 要考察的算法输出的一个hypothesis,在这里就是识别某字符是否为8的一个算法,我们希望它尽可能地接近c

这里“尽可能地接近”的意思是,有比较大的概率(Probably)得到的结果在大部分情况下(Approximately)与c一致。更严格地定义PAC-learnable如下:

集合C为PAC-learnable是指对于其中的所有concept c,对于任意分布D,对于任意小的数0 < eps < 1/2和0 < delta < 1/2,我们要考察的算法有至少(1-delta)的概率输出一个h满足P[h(x) != c(x)] <= eps,并且算法花费时间与 1/eps, 1/detla成多项式关系。

经典PAC framework的限制是(1)映射的值域只能为离散值(2)数据不能有噪声。针对这两个缺陷的扩展也有相关的研究。

参考资料

http://en.wikipedia.org/wiki/Probably_approximately_correct_learning
http://citeseer.ist.psu.edu/haussler92part.html

NLP笔记(2): 机器翻译之噪声信道模型

本文来自著名的论文[Brown 90],基本理论已经被讲滥了,所以这里只简单地提一下。设我们手里有的是法语句子f,要把它翻译成英语句子e,也即找到一个e使得P(e|f)最大。由Bayes定理,P(e|f) = P(e) * P(f|e) / P(f)。这里P(f)固定,故我们要找的就是一个e使得P(e)*P(f|e)最大。从噪声信道(noisy channel)的角度来分析就是,在我们头脑里按照P(e)生成了一个英文句子,结果在被我们说出或写出的时候发生了噪声干扰,这个干扰的概率分布是P(f|e),最后表现出来的就是一个法语句子了。

由此,一个统计机器翻译(SMT)系统的任务就分为了三部分:
(1) 估计P(e),即所谓的语言模型
(2) 估计P(f|e),即所谓的翻译模型
(3) 用一个合适的算法找到一个e使得P(e) * P(f|e)最大(至少是尽可能大)

当初在看到这里的时候我十分不解,相信所有人都会有这个问题:为什么不直接估计P(e|f)然后直接取最大概率的e?在很久以后我终于看到一个比较令人信服的解释(貌似是 Kevin Knight 的文章里写的?记不清了……):如果我们能够把模型估计得足够精确的话,实际上直接计算P(e|f)应该是更好的选择,然而由于数据集有限,这个估计不可能精确,所以往往得不到很好的结果。如果是用P(e)*P(f|e)来算的话,当然P(e)和P(f|e)也不会十分精确,但让这两者相乘,我们就可以期望找到一个P(e)和P(f|e)都不太坏的翻译,也就是说,这个翻译既比较像一个正常人说的英文,又和原来的法语意思比较接近,如果这两者中任何一个比较不靠谱的话,这个乘积就会比较小,从而也就不会被选出来。

话说这种噪声信道模型最初来自语音识别,不知道当初IBM那些研究人员是直接把理论搬来用的,还是真正比较了一下这个模型和用P(e|f)直接估计的效果,然后才决定用前者。总之,这个东西虽然理论上挺像那么回事,但总让人感觉(我个人感觉-_-)有点玄,实际上Och后来的实验也出现了该理论不能解释的结果,并最终导致更为一般的最大熵翻译模型的出现。这是后话,以后再提。接下来准备详细记一下这几个模型的估计以及搜索最佳翻译的算法。

奥卡姆剃刀的一些引申

这是翻看 Tom Mitchell 的老书《机器学习》时偶然看到的一些讨论,在Chapter 3.6的最末一段,感觉很有意思,不知道我理解得正确与否。

奥卡姆剃刀(Occam’s razor)是一个在哲学和自然科学里被广泛应用的原理,用中文来说就是“如无必要,勿增实体”。自觉或不自觉地使用这个原理似乎是人类的天性,例如在自然科学里,如果有两种处于竞争地位的理论都可以很好地解释某种现象,则人们一定会倾向于表述简单的那种理论,例如日心说之于地心说,例如“以太”的被否定,再比如多少人孜孜以求的“大一统理论”。我们貌似一直都有一种信念:这个宇宙是可以被尽可能简单地解释的。

然而这里还有一点问题,这里的“简单”是如何定义出的?在信息论里有一个最小描述原理(Minimum Description Length Principle),把一个事物的复杂性定义为表述它所需的最小长度。然而我们可以认为这个长度是与agent相关的,在计算机看来,可能是0/1串的位数,在我们人脑看来,可能是某些与生俱来的不可再分的概念的数目。所以可能就会出现一个问题,面对同一种现象,因为对概念的内部表述不同,不同的agent会倾向不同的理论,而他们的依据都是奥卡姆剃刀原理。例如,我们地球上的人类认为欧氏几何是天经地义,但对宇宙另一处演化出的智慧生物来说也许非欧几何更加自然。

文章最后提出了一个有点诡辩意味的观点来解释为什么我们倾向简单的理论。考虑一堆可以进化的计算机程序,我们把奥卡姆剃刀原理“写死”在它们的代码里面,使得这一部分不可能随着进化而改变。假设这些程序随着遗传、变异、优胜劣汰,若干代以后它们会越来越适应周围的环境(从外界人类的观点来看,它们能越来越好地解决我们的问题),我们会发现这些程序会逐渐改变它们对概念的“内部表述”,使得奥卡姆剃刀在现在的表述下能更好地适应环境。因为奥卡姆剃刀是被写死的,改变内部表述比改变这个原理相对容易得多。由上所述,实际上我们是先强制剃刀原理成立,结果我们就会发现进化出现的agent恰好就让它成立了。这实际上是一个倒因为果的解释,但却也未必不合理。把上面的程序改成我们人类自己,那就是说,上帝为这个宇宙设立了奥卡姆剃刀原理,我们人类经过长期的进化,终于使自己的基因本能地接受这个原理,因为只有这样才能更好的繁衍下去。呃,这么说是不是有点囧……