Monthly Archives: April 2009

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

Posted by on April 30, 2009 1 comment

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

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 (上)

Posted by on April 19, 2009 No comments

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

概率模型与前面的向量空间模型有所不同，在向量空间模型里，把每篇文档看作一个向量，通过比较文档向量与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，排序即可。

累死我了，下次继续。

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

Posted by on April 15, 2009 5 comments

摘要

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

正文

最近很多说法在互联网上流行，比如“一起坐摩天轮的恋人最终会以分手告终”，“情侣去过紫竹院的和送过石头记的一定会分手”[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.

正则二分图的完美匹配

Posted by on April 9, 2009 5 comments

所谓正则二分图，就是说左子集和右子集同样大，且所有点的度都相同。如果所有点的度都为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: 我为何而生

Posted by on April 3, 2009 8 comments

叔本华说：

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

伯特兰罗素说：

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

保尔柯察金说：

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

奈良鹿丸说：

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

贫嘴张大民说：

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

你我的回答，是什么？