Yin's Space

上午起来就感觉好像感冒了，然后整个人一天都有点昏昏沉沉的。刚才喝了点热水，睡了两个小时，出了一身汗，好像好了点。不管怎么说，harbin regional结束了，咱作为“出题人”之一说几句。事先声明一句，可能没有多少有用的，都是流水帐，所以不要期待能获得多少有营养的信息。

首 先这个“出题人”打上引号是因为我其实没干多少活。明白说起来的话，和我真正有瓜葛的也就是三道题：自己出的两道中等难度的题，一个放了网络赛，还有一个 就是所谓“现场赛倒数第四简单”的D；然后去年和mostleg在msra时讨论的一个问题的算法也被他拿来这里出了出来，就是H题"Offset Recovery"。然后验了几个小题的数据，比赛之前大概跟负责人说了说我对这几个题难度的评估分级等等，仅此而已。具体的组织、定夺、管理等脏活累活 全没参与，基本没出什么力就赚了点劳务费还有个纪念衫，说起来也应该是最悠闲最坐享其成的那一批人了。

说这些的第一个意思就是想说，其实这 个regional我没出多少力，代表不了“HIT官方”。进行得是成功还是失败，和我都没什么关系，就算做得好了也轮不到我受表扬，做得差了也轮不到我 受批评。当然作为原ACM@HIT的一分子，我自然是希望regional能成功，举办方、比赛方皆大欢喜。所以最后看到sunner给我发来的那一句“ 一切正常”之后，还是不禁松了一口气，幸好没出那种不可弥补的篓子，也算是多少没耽误大家一年来的苦练。

赛前孙大烈老师就跟我们说过，出题 人是哪些，大家基本也都能猜得到，所以说要“保密”。其实有些时候也挺无奈的，被别人问起我出不出题，“我出了”这三个字自然是不能说的，可是如果说“我 没出”的话到最后肯定会被他们指着鼻子说我瞪眼说胡话。所以也只能哼哼哈哈的打打太极拳，但其实这么做也就相当于是默认自己出了题，或者最起码不是一点关 系没有的。所以这个“密”其实也早就不算秘密了。

当时的想法就是不要太BT，所以也没想难为谁——最起码我出的那个D没难为到谁。就是枚举 一下两边2^8种组合，然后求个最小费用流就完了。唯一一层“窗户纸”就是可能有人会想枚举出具体的两两配对方法C(8, 2)C(6, 2)C(4, 2)C(2, 2)然后再具体判，这样就很纠结。当时验证数据的第一个人就是这么想的，纠结了一下，不过过一会就想通了。就这样，能达到这个效果我就已经非常满意了。所 以最后这道题做出来的人也挺多，基本就是被人狂切的水题。那个H，当时在msra和mostleg讨论了一阵子，也没纠结到什么程度，第一版的想法就是类 似sweepline algorithm，维护一个结构（当前的表达式），然后维护一个事件队列，每次更新表达式的值就好了。至于写起代码来是有一点小trick，当时第一版 标程是越了数据范围，后来还是mostleg发现了才改过来。好像也就这点东西了。 至于出了两个费用流这个我也没想到，当时一致认同就是要把这两个题分开，不知道为什么最后又换到了一起。

说说我对其他几个题的感觉。A题当 时看到之后就感觉应该有人会用dancing link去做，由于这一阵子这东西炒得挺热，经常看到有人在xiaonei上发状态“DLX太NB了”“终于用DLX干掉某题了”之类的话，我还以为会有 不少的人过。其实我感觉出题人根本就不知道DLX这个东西，他虽然是ACM@HIT元老级人物，但是早就工作了，应该没时间去接触这种新兴事物。就总体来 说，其他的题至少比这个靠谱些，fishcanfly在验完数据说这道题“至少随便写写的搜索是过不掉的”，所以最后没几个人过也还算可以理解。F当时一 看名字叫mission impossible，读了读题，再看了眼出题人，我就明白这应该不是给人做的题，反正也不需要我写验证，所以就直接pass掉了。C是当年我们队计算几 何主力的fishcanfly出的，猜都能猜到会很纠结，鱼教主在虐人与被虐两大领域都有极深的造诣，绝非我等所能企及，而且我对计算几何的编码一向不太 感冒，所以根本就是理论AC掉就算了。最后好像也都说卡得挺惨淡的。

赛前说最好要所有人都过题，所以我就算是半严肃半认真的说话，建议最好 来个“侮辱大家智商”的题。因为我感觉其实想都过题确实不太现实，因为只要稍微上点水平，就总会有那么一两个队伍因为各种各样的原因导致最后一个题都没 过。最后那道临时加的水题究竟水到什么程度，我也不知道。事实也确实是，佳木斯大学在那道临时水题上卡了那么久都不过，我还以为这个目标要落空了呢，没想 到最后还真过了。就算明知是最后一名，也要努力到最后的精神，是我所缺少的，很值得我尊敬。

题目总体来说好像是有一点难，因为除了白送的题 似乎也没有多少写起来方便的。所谓我的那个“水题”也是需要拍不短的费用流模板，更被人说为什么会有两个费用流的题。这种事情我也只能向大家说抱歉，我虽 然不能说是这件事情的主要负责人，但是我确实还是有点责任的。当时已经有一阵子没写代码了，看道题也大多都是以“理论AC”为目的，所以各方面能力都有退 化，导致错误的估计了一些题目的实际难度，给了组织者不少的错误建议。在这里代表我自己，跟那些不满的人说一下抱歉。

不管 怎么说，能顺利的结束，没有出那种不可饶恕的错误（比如说组织不力、甲流大爆发、题目捅出了大篓子之类的），我感觉剩下的希望大家还是能多包涵。毕竟不可 能有比赛是绝对公平的，也不可能有题是适合每一个队伍。至少这次我以一个半局外人的观点来看，能让好些平时很少出彩的队伍和学校扬眉吐气，也算是一种成功 了吧，至少他们多年的努力终于有了回报不是么。

以上。

一个计数问题。给定一个数N()，问N个点N条边的labeled connected graph有多少个。用英语说简单点，中文有点纠结，就是顶点可区分的连通图个数。

这道题我感觉很有一写的价值，至少对我而言，纠结了我好几天。为了搞定它，这几天想了很多种方法，走了无数错误的路线，甚至异想天开的在wikipedia上狂搜二维生成函数的资料看。问题没解决，新知识倒是学了不少。最后还是灵光乍现，想到了一步重要变换，问题才迎刃而解。不过我也只是得出了数学解，到现在我也没有找到对这个公式的直观解释，所以还望牛人释疑。

好，下面言归正传。其实大家一打眼就能看出来，N个点N条边还连通，那实际上就是一棵树上带着一个环。我的一个想法（预先提示一下，完全错误的想法）自然就是枚举环上的点的个数k，共有种可能。剩下的N-K个点呢，自然就是分成一些组连在一起，然后再挂在这个环上。假设分成了m组，这样每个组挂在长度为k的环上的任意一处，共有种可能，而N-k个点分成m组，每个组组内的元素还顺序还不可忽略，这不就是个第一类Stirling数么，也就是。所以再枚举一下组的个数m，总的表达式就变成了。观察一下能发现，后面这个对m求和的东西，正好就是第一类Stirling数的生成函数取在k点的函数值。这样的话整个式子就变成了，而这个东西稍微动一下脑子就可以在的时间内算出来。整个问题好像解决了，还完美的用到了第一类Stirling数的生成函数，不是么？错了。因为每一个组挂在环上并不是k种选择，否则就是默认每一个挂在外面分支只能是一条线，而实际上挂在外面的分支可以是多种形态，对吧。所以这种方法悲剧了。这是我的第一个想法。

好。下面换一个思路，从另外一个角度考虑问题。考虑一下每种可能的结构，它要么有叶子（就是指度为1的点），要么没有叶子。没有叶子的含圈的连通图就是一个圈，所以第二种很简单就能计数，应用第一类Stirling数有结果。第一种有叶子的，假设叶子数为k，我们就可以先删掉一个叶子，这样剩下的图是一个N-1个点N-1条边的连通图。可能敏锐的人已经发现了，这一段弄好了可以动态规划，所以需要仔细的设计一下。删掉一个叶子之后，整个图还会剩下多少叶子呢？可能有k-1个，但是可能仍然存在k个，因为删掉叶子之后，它连接的点可能会变成新的叶子。所以我们需要把图的叶子数K也加入动态规划的状态。对于一个M个点K个叶子的树，用代表它的结构个数，加入一篇新的叶子，如果叶子数增多了一个，那么连接的点必然就是内部节点，选择共有M-K种；如果叶子数不变，那么必然连接的是叶子，选择有K种；由于顶点可区分，所以原始M-1个点的树中顶点编号的组合共有种，还要再乘以一个M。但是这样计数又会发生重复，因为K片叶子的树的每一个叶子在计算的时候，都把这棵树算了一遍，所以还要除以一个K。总的来说，就会出现下面一个递推公式：。边界条件即为。以这个公式计算，就会得到一个的动态规划算法。

这种计数法是没错的，而且没有什么纠结的地方。但是很明显，如果的算法就能解决这个问题，那世界也会清静许多了，本日志也就没有任何存在的价值了。所以不用多说，算法最后的下场就是可耻的失败鸟。这迫使我们不得不对上面这个递推式做更进一步的优化。很明显，上面的式子可以等价写成下面的形式：;。我们注意到，将这个递推式稍微改写，就可以变成下面的形式：。有发现什么了吧，如果令，上式则可变为。

问题到这里好像陷入了僵局。这个方程似乎没有什么很好的办法求下去了，似乎又是一步死路。不过且慢，你会发现两类Stirling数的递推公式和它非常的相似，如果能尽量的向其靠拢，或许会出现转机。所以，我们可以考虑一下下面这个数。令，带入上式，则会发现递推公式变成了下面的形式：。对，不用揉眼睛，你没看错，这不和第二类Stirling数的递推公式完完全全的吻合么？然后我们再仔细看一下我们要求的东西变成了什么。是M个节点中有k个叶子的该图的个数，而由于这个图中有一个环，环上至少有3个点，所以叶子数最多也就是M-3，我们要计数的东西其实是。把这个公式中的T用F带入一下，就是。有没有发现这个是什么东西？这个不就是第二类Stirling数的生成函数在M点处的函数值么？F的递推式又正好满足第二类Stirling数的递推表示，这不就可以仿照求第二类Stirling数生成函数的做法去做了么？

所以，下面的步骤其实就很简单了。令。要求的就是的函数值。回想一下第二类Stirling数生成函数的求法，根据公式带入，即可得到一个关于g的递推式：，初值为。根据这个递推式，很容易就可以得出一个在时间内计算任意的算法，递推时顺便将带入即可。

PS: 这个递推式是否能更进一步的简化，也就是说，直接求出个closed form来，甚至设计一个的算法？这个我暂时就不知道了，没什么精力去做了。的算法已经够了。另外，有牛人能直观的解释一下这个公式的道理么？

再次进入了“讨论状态”，这次是和陈硕。所谓的“讨论状态”，相信和我长时间讨论过一个问题而且观点完全对立的人都体会过，就是咄咄逼人，得理不饶 人，穷追猛打，你死我活的状态，只是不含人身攻击与辱骂词语，完全是言语上的交锋。这还是说得好听点之后的结果。然后呢？然后，现在又得和人家道歉，怕自 己冒犯了人家。不是被迫的，也不是因为任何理由，只是因为良心不安，完全自发的。应该还是我太认真了，至少在一些重大的问题上，我感觉自己眼睛里还是挺难 容沙子的。我感觉这可能是我永远也无法改掉的坏毛病了。对学术研究来说，这是一个好品质，但是这并不是一个为人处世的好特质。

其实能感觉到，心里还是有一种激情，我说不上来是什么，但是表现出来的就是我仍然有兴致去反驳一个明显错误的结论。看来我的心态还没有完全的变老啊，不错，不错。

最近的工作海量的多，包括各种作业与代码。Convex Optimization的习题工作进展缓慢，刚把Convex Set那章的习题做完。感觉这一章所有习题中最难的部分全都集中在最后一节dual cone and generalized inequality上了，做得我步履维艰。就算是很努力地去想，也还是有数个题没有解决。我知道这是慢功夫，但是时间不等人，这种时间的流逝让我感觉焦 虑。唔，还是要煞下心来啊。往好了想的话，至少比我预想中的好多了，我还以为大多数的题我都做不出来呢，真正做了才知道，原来这好些题还是很简单的啊。虽 说步骤繁杂了许多，不过我感觉这就像当年我写的第一道ACM题一样，代码也是冗长繁复，现在看起来都感到可笑。不过我相信经过常时间的磨练，这些数学的功 底也会和我的算法分析能力、编码能力一样，逐步提高，最后达到随心所欲的程度。现在就算是我迈出的第一步吧。

自从去年3月份注册开始，直到今天在newsmth发满了1000个帖子。这个整数当然是献给了Algorithm版，呵呵。想一想，混的这一年半以来长了点眼界，但是水平却没有太大的提高。也是，缺少了高强度的锻炼，怎么能进步呢。

但愿，我能实现心里的那个目标吧。虽说，我现在确实表现得有一点急功近利了。

本来以为水杯是放在实验室里的，结果……结果今天早上一看，不见了。想一想，好像昨晚走的时候确实带了，可是为什么还跟她说我没带呢…… 好像丢的地方也只能是卖水果的地方或者打印店了。前一段时间王丽萍丢了雨伞，最后凭借其自身无敌的人品终随手就找了回来。现在轮到俺了，真的能有好运气 么……

昨天打印了Convex Optimization，整整730页，按章节装订，厚厚三大本，手握不住。我还以为怎么着也得花个六七十块钱，结果没想到最后算上王丽萍44页的诗歌鉴赏加起来才55块整。顿时感叹他们赚钱真的好不容易啊。是不是自己也应该爱惜一点呢。

昨天听邢远见亲口爆出的他的劲爆新闻，群里顿时人声鼎沸，各方贺电络绎不绝，呵呵。恩恩恩，按照当事人的话说，“为了不让mm有太大的压力，还是不要公然传播好吧”。所以呢，昨天的报料和各种八卦资料今天全部让我毁尸灭迹鸟。不过在这里还是bless一下吧。

以上。

好像做了两段……

第一段是自己突然又回去做了场TC SRM，打开题之后发现自己做的是div II，狂切掉三题之后居然系统又自动转到了div I，花了好长时间做完easy和一半的medium之后比赛结束了。然后仔细看一下分数分布发现这三题的满分是5, 1150和1175，我5分的easy得了75分的得分，medium没做完但是却离奇的被submit上去了……之后发现ranklist里面海量的人三题通关，但是我做成这种半吊子却莫名其妙的排了18名。呃，再然后……然后就不记得鸟……

第二段是一大堆人围在一起，中间坐了一个boss级人物（忘了是谁了），向大家逐一介绍每个人。在介绍到XXX的时候突然说这个女生是我mm。囧r囧r囧rz……然后……然后又不记得鸟……