Monthly Archives: April 2009

宁波理工邀请赛TJU-Team1总结

题目现在好像还看不到,据说过段时间会挂出来

A. 简单来说就是求第n个catalan数 MOD m的值,n可能到10^6,m是10^9

B. 搜索题,据说是很裸的dancing link,不过我不懂

C. 处理两个list的运算,比较简单

D. 一堆窗口,一堆点击,每次点击就把点到的窗口拿到最上层,输出每次点击后位于最上层的是谁

E. dp,背包问题,不太难

F. 树型DP,在树上找一条长为L的链使得其它所有点到这个链的最近距离之和最小

G. 很有意思的题,后来我们讨论似乎可以用解方程组做

H. AC自动机+状态压缩BFS

I. 比较简单

J. 区间覆盖问题,贪心

一上来zdx跟我说A可能能做,我一看Catalan么,结果发现O(n)的递推式忘掉了-_-,我们一点关于组合数学的资料都没带,然后我就开始手推。小刘说I是水题,就上去写了。推了很久推出来了,突然才意识到里面有个除法,没办法直接取模的,当时就囧了,怪不得一直没人过呢。小刘的I题WA了,zdx说C题能写,她就上去写了,小刘自己找错,我开始读剩下的题,想找找有没有我所谓的“条件反射题”,结果越读越囧:A题这种我只知道一种理论上把m拆成互质的,然后分别算出逆元来,最后再用中国剩余定理合起来的方法,但是数论题我从来就不会做的,扔了;B题明显搜索,明显不敢写,扔了;D题一看数据规模就吓死人,几万个窗口,几十万次点击,扔了;E题想了一会儿,有点想法,但复杂度有点悬,扔了;F题感觉是状态转移超级恶心的树型DP,扔了;G题想出一个线性规划,扔了;H题没想到做法,扔了……这时候就傻了,怎么没有能做的题呢?本想跟跟风,扫遍全场只有CI两题,无奈了。

zdx的C也WA了,小刘的I又WA了一次后,我发现了她程序里一个小bug,12点应该显示成0点的,改了以后就过了。然后她跟我说了J题题意,说感觉是贪心,我一开始没想法,以为是dp,后来仔细想想确实可以贪心,正好这时候lx他们队有J球出来了,我就直接把一个O(n^2)的程序拍了上去(n是10000…当然加了一堆break在里面,后来我们分析加上一个剪枝后应该可能是线性的,但不知道我当时是怎么写的了),总之是y了……这时候zdx的C又WA了一次,她说找不出错了,让我重写一下。我仔细一想也不太复杂,重写也不花太长时间,于是重写一遍y了。这时候E过了很多,再加上有J题乱暴过了的信心,对这题的复杂度也就放心了。用了一个O(n*m)的预处理,然后二分答案再二分查找每个物品的花费,中间写卡了,大概花了40多分钟y了。然后又无所事事了……

当时的情况是,还有一个半小时,我们左边的队很诡异地过了当时好像全场唯一的D,右前方的复旦队过了个F,大概有3个H,还有1个A。因为看到有学校一个多小时就过了H,猜测这题可能结论性比较强或者是模版题,就决定先想想试试,如果不行只好冒个挂死的危险硬啃F。还好突然灵光一闪发现就是个自动机的变形,把自动机建起来以后用个BFS,用状态压缩记录一下状态就可以了。复杂度比较变态,我开了若干个几千万大小的数组……心惊胆颤地写完了,又调试了半天才过Sample,比较虚,又让小刘和zdx出了一些数据,果然又发现了bug,然后还好还是1y了……到那时为止我的所有提交都是Yes,发现和MM组队果然有好RP啊……

还有半个多小时,F题不敢开了,考虑到我们左边不太强的队过了D,心想或许能水过去,就开始乱水。结果水出来无数TLE,一直到比赛结束。结束以后问了问也过了这题的WHU,他们的做法是先离线读入所有点击的位置,然后再处理一下怎么怎么的,这题还没有仔细想。

后来回来的火车上小胖说了一下G的想法,我感觉挺强大的:其实我们可以把这个网络看成一个电路,那个S(u,v)其实就是两点间的电势差,这样当源汇点之间的电压一定时,电流也是一定的,故这个方程组的解实际上是唯一的,只不过可能同时放大或缩小一个比例而已。这样就不需要线性规划,只要解方程组出来,再把解缩放到恰好满足流量限制就可以了。如果当时能想到这个的话,半个多小时写个高斯消元还是有可能的,这样就6题了,嘿嘿,yy一下……

这次的题目出得很好,等题目挂出来以后建议大家都去看看。最后点评的时候,蔡老师说有点偏难了,实际上我感觉是因为大家基本都是临时凑的队伍,少有以磨合好的阵容参赛的,所以成绩偏低,我想如果这是一场regional的话,冠军肯定远不止6题。

另外,学到一种扑克新玩法。还有,拱猪拱了数晚上,我只输过两把,呼呼哈哈

IR笔记(8) – Probabilistic Model (上)

其实这个我还是有点似懂非懂,请多指教了。这一篇全是公式,呃……

概率模型与前面的向量空间模型有所不同,在向量空间模型里,把每篇文档看作一个向量,通过比较文档向量与Query向量的夹角来计算相似度,而概率模型中,我们考虑的是给定文档和查询,估计出这篇文档是相关文档的概率,即P(R=1 | d,q),(这里d,q分别表示文档和查询),然后把所有文档依此概率值排序。

这个方法看起来是比向量空间模型更靠谱的,但在实际计算中,即使做了相当强的简化,仍然有很多的困难,导致在相当长的一段时间内概率模型的效果比不上向量空间模型。下面具体说一下计算方法:

首先要简化原问题,不考虑TF,只考虑一个词在一篇文档中有没有出现,只有0,1两个取值,这样得到的模型叫BIM。为了后面的形式上简便,我们计算所谓的Odd:

$$O(R|x,q) = frac{P(R=1 | x,q)}{P(R=0 | x,q)}$$ (这里x表示把d二值化以后的向量)

由贝叶斯公式得

$$!O(R|x,q) = frac{P(R=1|q)}{P(R=0|q)}frac{P(x|R=1,q)}{P(x|R=0,q)}$$

容易发现等号右边的第一个分式是与ranking无关的,故可以无视。再假设各单词之间是独立的(类似Naive Bayes里的假设),则有

$$!O(R|x,q)=O(R|q) Pi_t frac{P(x_t|R=1,q)}{P(x_t|R=0,q)}$$

再分x_t取0,1的两种情况:

$$!O(R|x,q)=O(R|q) Pi_{t:x_t=0}frac{P(x_t=0|R=1,q)}{P(x_t=0|R=0,q)} Pi_{t:x_t=1}frac{P(x_t=1|R=1,q)}{P(x_t=1|R=0,q)}$$

然后我们再做一个假设:没有在query中出现的单词,它出现于相关文档和不相关文档的概率是相同的。这样我们就只需考虑在query中出现的单词即可。

我们定义$$p_t=P(x_t=1|R=1,q), r_t=P(x_t=1|R=0,q)$$,于是有

$$O(R|x,q)=O(R|q)Pi_{t:x_t=q_t=1}frac{p_t}{u_t} Pi_{t:x_t=0,q_t=1}frac{1-p_t}{1-u_t}$$

$$=O(R|q)Pi_{t:x_t=q_t=1}frac{p_t(1-u_t)}{u_t(1-p_t)} Pi_{t:q_t=1}frac{1-p_t}{1-u_t}$$

我们可以发现最右边那一项对所有x_t都要计算,所以又与ranking无关了,于是只剩下的中间那个,定义文档的Retrieval Status Value (RSV):

$$!RSV_d = sum_{t:x_t=q_t=1} logfrac{p_t(1-u_t)} {u_t(1-p_t)}$$

则理论上,我们计算出所有的文档的RSV,排序即可。

累死我了,下次继续。

学术帖:从概率统计论角度分析为什么“情侣去过某某地或者送过某某东西就一定会分手”的说法这么准?

摘要

本文从学术角度严肃探讨了“情侣之间送过某某东西或者去过某某地就一定会分手”等等说法看上去很准的原因,为广大情侣们摆脱困扰,合理开展增进感情的活动提供了理论依据。

正文

最近很多说法在互联网上流行,比如“一起坐摩天轮的恋人最终会以分手告终”,“情侣去过紫竹院的和送过石头记的一定会分手”[1]等等,每次此种言论后均有大量回复证明此看法的准确性(虽然也有少数反对声音)。实际上,这种说法是没有统计学上的依据的。

定理1: 若全社会平均每个人的谈恋爱次数大于2,则分手的情侣一定比最后在一起的情侣多。

定理1的另一种表述是,若社会总体分手率大于50%,则分手的情侣一定比最后在一起的情侣多。而实际上,资料显示情侣分手率高达80%[2]。(因此以frequentists派的观点来看,根据极大似然估计,对任何一对情侣,我们都应该预言其以分手告终。为避免被情侣们追杀,本文对此不作展开)

定理2: 任何事件(即“去过某某地”或“送过某某东西”等),只要不与“情侣分手”这一事件成很强的负相关[3],这种预言就总是看上去很准确的(比如,准确率>50%)。

设“去过某某地”这一事件为a,“分手”这一事件为b,P(b|a)即为预言的准确率。我们首先考虑相关性为0的情况,此时P(a,b)=P(a)P(b),则P(b|a)=P(a,b)/P(a)=P(a)P(b)/P(a)=P(b),可见,在相关性为0的情况下,预言的准确率仅与P(b),即全部情侣总的先验分手概率有关。而据上文所述,P(b)=80%>50%,P(b|a)这个预言就给人以很准确的假象。

进一步地,在相关性非0的情况下,我们还可以求出一个阈值theta,任何与b相关性大于theta的事件,P(b|a)发生的概率都大于50%。因为公式稍繁琐,在这里就不作推导了。

[附注:如果要发Paper的话,下面这段解释应删除]
其实用大白话来讲就是,就算你啥都不管,它的概率就已经是80%了,那么你尽可以提一些莫名其妙的无关情况(即事件发生的相关性为0),它准确性当然还是很高。实际上,坐不坐摩天轮和分不分手之间根本就没有关联,坐了的也是80%分手,没坐的也是80%分手,你找10个坐了的出来,里面就有8个是分手的,它当然看上去就准确了。这种情况的一个极端是,我预言“所有今天吃米饭的人一百年后都会死”,这准确性基本100%,但这是因为一百年后会死的概率本来就是100%,跟吃不吃米饭没啥关系。

下面总结一下设计这样一条预言应遵循的原则:
1. 事件b的先验概率应该足够大(比如,情侣分手率)
2. 事件a不能与b成强负相关(比如“已经订了婚的情侣一定会分手”这就不太靠谱了)
3. 为了更具迷惑性,事件a最好不要与b成强正相关(比如“每天吵架的情侣一定会分手”这预言虽然没错,但别人兴趣也不会很大,只会觉得你在说废话),而应该与b没有相关性(比如本文开始的例子),这样就会给人以神奇的感觉。
4. 为了更具广泛性,事件a应该选择很多人会做的事(比如情侣之间送什么东西),这样才能使得你的预言被广泛传播(要是说“一起登过火星的情侣一定会分手”估计没人理你的)

参考文献
[1]http://www.douban.com/group/topic/4939331/
[2]http://news.163.com/06/0704/01/2L5ABBL200011229.html
[3]http://en.wikipedia.org/wiki/Correlation

Note: This paper will appear on Special Interest Group on Lovers Retrieval (SIGLR) 2009.

正则二分图的完美匹配

所谓正则二分图,就是说左子集和右子集同样大,且所有点的度都相同。如果所有点的度都为d,这个二分图就叫做d-正则二分图。

有个Hall定理想必大家都听说过,我在这里不证了,只把结论说一下:

对一个二分图,若对任何左子集X的子集S,满足|S|<=|N(S)|,则该二分图存在完美匹配(这里N(S)表示S的邻集,即在右子集Y中与S中的点有边相连的点的集合)

由此可以得出一个推论:一个d-正则二分图必然存在一个完美匹配。证明也很简单,考虑左子集的任意一个子集S,设k=|S|,则必然有dk条边与其相连,而这dk条边必然连到右边至少k个点上(因为每个点最多连d条边)。实际上,我们可以有更进一步的推论:

一个d-正则二分图存在d组完美匹配,且这d组匹配的边都互不相同。

证明同样简单,由上已知d-正则二分图必存在完美匹配,那么我们把这个匹配的边从图中拿去,就得到了一个(d-1)-正则二分图,于是仍存在完美匹配,继续进行,故得证。

到这里为止没有什么新奇的内容,促使我写这篇Blog的原因是下面一个有意思的问题:如何能尽可能快地为d-正则二分图找出一组完美匹配?

我们知道一般二分图的最大匹配算法复杂度是O(VE),而Hall定理只告诉我们完美匹配存在,却没有求匹配的方法。下面我们来看一个针对特殊d值的神奇算法,下面的算法要求d是2的整数次幂:

因为d为偶数,我们一定可以用O(E)时间在d-正则二分图中找出一个欧拉回路。然后,我们把这条欧拉回路中的边隔一条删掉一条,因为对每个点来说每一对入边和出边都恰好留下一条,你会发现得到了一个(d/2)-正则二分图。重复上面算法直到d=1,则完美匹配显然可得。而我们会惊奇地发现E + E/2 + E/4 + … = 2E,所以总的复杂度还是O(E)。

上面这个神奇的算法来自Gabow, Kariv [STOC78]。对于一般的d值,想找到一个线性算法并不容易,这个任务直到2001年才由[Cole-Ost-Schirra]完成。而在SODA09上,对于大于sqrt(n)的d值,[Goel-Kapralov-Khanna]给出了一个sublinear的算法。这只是我从一篇资料里看到的简介,具体的算法想必非我现在可以明白的了,有兴趣的读者可以自己去研究下。

The Big Questions: 我为何而生

叔本华说:

除以受苦为生活的直接目的之外,人生就没有什么目的可言。我们观察世界,见事事处处,都充满痛苦,都原于生活本身之需要,且不可分离,真可谓毫无意义可言,不合于道理。个别的不幸,固然似为不期而遇的事物,但作为通常的不幸,则事出一辙,可见是必然的。

伯特兰罗素说:

对爱情的渴望,对知识的追求,对人类苦难不可遏制的同情,是支配我一生的单纯而强烈的三种感情。这些感情如阵阵飓风,吹拂在我动荡不定的生涯中,有时甚至吹过深沉痛苦的海洋,直抵绝望的边缘。

保尔柯察金说:

人的一生应该这样来度过:当他回首往事时,不因虚度年华而悔恨,也不因碌碌无为而羞耻。在临死的时候,他能够说:“我的整个生命和全部精力,都献给了世界上最壮丽的事业——为人类的解放而斗争。”

奈良鹿丸说:

我啊,只想安稳地做个平凡的忍者,安稳地生活,和一个不美也不丑的女人安稳地结婚,安稳地生两个小孩,第一个是女孩,之后是男孩。等女儿结了婚,儿子独立后便退休,之后闲时和朋友下下象棋或围棋,过着悠哉悠哉的隐居生活,然后先老婆一步离开这个世界。

贫嘴张大民说:

有人枪毙你,没辙了,你再死,死就死了。没人枪毙你,你就活着,好好活着。

你我的回答,是什么?