Tag Archives: ACM

Re: 真的ACM很有用么?

最近一直懒得写文章,把今天在水木回复的一个长文贴一下,同时也是为了表明上一篇《ACM伤不起》纯属调侃之作,其实我对ACM比赛和ACMer有很多很多的爱啊~

==========================================

发信人: RoBa269 (弱吧), 信区: Programming
标  题: Re: 真的ACM很有用么?
发信站: 水木社区 (Sat Aug 13 21:32:03 2011), 站内

作为一个搞了多年ACM但没有什么成绩,目前刚刚入职几个月的菜鸟,我来随便胡说几点。写到最后发现有的地方稍微偏激了点,不过懒得改了,欢迎楼下来拍。

1. ACM竞赛不是搞研究,但是搞过ACM的学生,至少不比不搞ACM的学生更远离科学研究,我甚至敢大胆地讲,从统计意义上讲ACMer会更喜欢搞研究。实际上,就我对身边和网上讨论群的观察,对计算机科学始终保持严肃认真态度的更多地是ACMer。在ACMer的讨论里经常动不动就出现形式语言、可计算性、编译原理以及最优化、概率、统计等等内容,而大部分通常的计算机专业学生往往也只把计算机科学简单地等同于编程而已。我本人就是在竞赛中领略过算法的优美之后,开始对计算机科学以至数学产生由衷的敬畏和赞叹。反观那些所谓的研究(尤其是在国内的学校),称得上研究方法、研究思想的又有多少呢?云山雾罩故弄玄虚来忽悠经费的就不提了,大学学报连某些基本的概念都弄不对,求最大流把最朴素的ford-fulkerson加个拍脑袋想出的heuristic,也不证明一下就敢宣称O(VE)的复杂度,还有什么调和级数既收敛又发散,这又算是什么研究方法呢?

2. ACM题目里确实有很多可以算作“奇技怪巧”的东西,但这些“奇技怪巧”正是若干年前研究论文里发表的内容。实际上为了解决某些ACM题,我们经常要去查阅过去的论文,ACM题目只是把论文里的内容放在了一个有实际背景的上下文里而已。用一个巧妙的数据结构把某一步操作从O(n)降到O(logn),如果这个解法之前没有被发表过,这样的“奇技怪巧”不正是一个绝好的论文题材么?难道只有NP=P这样的大问题才值得研究?

3. 因为版上前面几个帖子讨论的是公司招人该不该看重ACM什么什么的,我就大胆地从公司招人的角度谈一谈这事。以我的观察,ACMer大都有这么几个优点:(1)聪明,并且知道比自己更聪明的人有很多。大言不惭地讲,这个竞赛还是需要一点智商的,以我的观察,参加这个比赛的同学在刚开始时大都是颇有点自负的,但是被各种大神虐几顿以后就会知道天外有天了。(2)对计算机有发自内心的兴趣,并且有持之以恒的精神。大体来讲参加ACM竞赛的功利性是比较小的(当然,随着ACM竞赛在国内越来越受到重视,不可否认现在竞赛的功利性变强了),要想得到个像样的成绩,如果不是出于真正的兴趣是坚持不下来的。不做比赛的同学平时可能也到OnlineJudge上随便做几道题,可能觉得没什么大不了,但是不是所有人都能有毅力坚持几年,做几千道题,写十几万行代码。题海战术你可以不赞同,其实我也不怎么赞同,但有这种毅力的人一定是有可取之处的。(3)基本功扎实。编程语言、算法、数据结构这样的课程就不必多说了,概率、离散、组合数学等等也都是ACMer日夜操练随手拈来的东西。因为很注重程序效率,ACMer往往也对汇编语言、操作系统、体系结构等知识有相对更深刻的理解。你可以批评说ACMer从来不写工程代码、变量名随意、代码风格不好、不考虑异常情况什么的,但那只是因为他们从前不关注这些。从公司的角度看,给新人培训代码规范,比起给新人培训算法数据结构等等一整套基本知识,哪个更容易呢?说到这里我觉得很多人有个误解需要澄清一下:ACMer会做ACM题,不代表人家只会做ACM题。如果一个ACMer能搞定那么多繁复纠结的算法,他学起工程性的东西来会很困难么?

以上是我猜测公司看重ACM比赛的几点最重要原因。相比之下,你是不是懂某个算法这件事本身并不是特别重要的原因。公司不是因为你恰好懂某些算法而招你,而是因为懂这些算法表明你更可能是一个优秀的人才。

【 在 lushan5436 (密如) 的大作中提到: 】
: 其实,有些不明白,
: ACM的学生,算不上搞研究吧,总觉得是小聪明。ACM题目总觉得讲究的是奇技怪
巧。
: 研究的方法,思想,总比这些技巧重要吧?。
: ……………….


“只要有你在,只要你微笑,那就是幸福。明明感到不安,却能够安心。只要有你在,光是并肩走路,我都觉得高兴。

只是短短的时间。因为林缝间的阳光似乎很暖和而停下脚步。你笑着说,总有一天我们能站在同样的地方。”

……我一直希望,有某人能这样跟我说。

※ 来源:·水木社区 http://newsmth.net·[FROM: 222.130.141.*]

天津赛区网络赛非正式题解

首先声明:因为大部分题目是请神牛来出的,有几个题目我只写了暴力的验证程序而没有实现可以AC的程序。我这里写的解法有的只是看标程猜出来的,难免有不准确之处。如果有不对的地方,也是因为我对标程的理解有误。题目本身的正确性是可以保证的,这个请放心。

A. 首先离散化,然后用一条扫描线从左向右扫描事件,要求一个数据结构可以动态增加和删除线段,并且可以查询恰好被覆盖了K次的区间长度。标程的做法是分块处理,把整个Y轴分成长度约为SQRT(N)的小块,这样一条线段的中间部分会覆盖若干整个小块,两端的部分逐元素处理。对每个小块,用一个hash表H维护被覆盖了i次的长度H[i],以及该小块作为整体被覆盖的次数q。查询时对每个小块查询H[K-q]即可。期望的时间复杂是O(N*sqrt(N))

B. 二分答案,用2-SAT验证。把每轮游戏看作一个布尔变量,有两种取值。假设所有圆的最小半径为r,如果不同轮的某两个圆心的距离小于2r,说明这两个不能同时选择。由此得到一系列限制条件,恰好组成一个每个子式都包含两个变量的合取范式,再判断这个2-SAT问题是否有解即可。

C. 很赞的题目。我们考虑用一个矩形框住所有点,如果要求矩形边平行于坐标轴,则容易发现结果就是简单的把x,y坐标求最值,得到矩形(minx, miny) – (maxx, maxy)。如果我们要求矩形的倾角为a,则可以把所有点都旋转a角度得到新的坐标,然后用同样的方法来做。一个重要的观察是,f(a) = (maxx – minx) – (maxy – miny)是随着a的变化而单调变化的。当a从0度增加到90度,f(a)的符号必然变化(当然,也有一直是0的特殊情况……),把f(a)=0的那个时刻用二分法计算出来就可以了。

当然,此题也有其他方法来做,不过这种方法我觉得是最简捷优美的。

D. 有点麻烦的表达式处理题,基本上大家都要WA几次才能过。注意负号是可以作为单目运算符的,而正号不行,比赛的时候很多人问这个地方。还有就是范围越界的情况可能要尤其注意一下。

E. 如果不考虑那个VIP,N个房间可以被最多K把钥匙打开的情况,实际上就是1..N的置换组成最多K个环的情况,这个就是第一类strling数之和S1[n][1]+S1[n][2]+…+S1[n][k]。在这些情况里面,如果钥匙1恰好锁在房间1里也是不行的,所以还要减去N-1个房间被最多K-1把钥匙打开的情况数。

F. 水题,O(n^2)直接写就可以。

G. 我还没看懂标程是怎么做的,貌似是很神奇的解法。此题题解待补充。

H. 数学题,求曲线积分以后可以得到耗能关于时间t的函数e(t) = X * sqrt(w^2*r^2+v^2) * (t*v*sqrt(r^2+t^2*v^2) + r^2*log(2*v*(t*v+sqrt(r^2+t^2*v^2)))) / (2*v),此函数关于t单调增,二分求解e(t)=E即可。注意特殊处理r=0的情况。

I. 如果四个点不能组成凸四边形,则必然是其中三个点组成一个三角形,另一个点在该三角形内部。于是我们可以O(n)枚举一个点作为内部中心,试图从其他的点里选出三个来,组成三角形把它包围住,看看有多少种可能的选择。继续观察发现,如果三个点不能圈住中心点,则必然是存在一条通过中心点的直线,使得这三点都在直线的同侧。于是我们可以把所有点(除了中心点)按极角排序,然后线性转圈扫描一下就可以统计出来了。总的复杂度是O(n^2*logn)

J. 最后的矩形一定是在四个方向都遇到了-1或者边界才停止扩张。预处理出每个点(i,j)向左能扩张到的点L[i][j],向右能扩张到的点R[i][j]。对每个查询,外层以y递增,内层以x递增的顺序枚举(x,y),假设此点是矩形的底部,并且矩形是向上扩张直到某个(k,y)为-1或边界(这里k<x)。则此时矩形的上边界为k+1,下边界为x,左边界为max{L[k+1][y], L[k+2][y], … L[x][y]},右边界为min{R[k+1][y], R[k+2][y], … R[x][y]}。因为x是从上到下扫描过来的,左右边界可以顺便更新。Special Area的选择就是在这个区域内选择一个最大值,这个可以用二维RMQ在O(1)时间内完成。总的复杂度就是O(N*M*Q)

K. 每当一个点x被mark的时候,对所有点对(i,j),更新cost[i][j] = min(cost[i][j], cost[i][x] + cost[x][j]),复杂度为O(N^2)。这种操作最多有N次,故总复杂度是O(N^3)

ZJU 2010校赛解题报告

Edit: 已经有官方完整版了 http://www.hhanger.com/blog/?p=438

抢在官方报告前发一个,为Blog增人气,嘿嘿。题目出得我觉得非常好,先写大家比较关心的D和G,以后再慢慢补全。比赛页面:http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=307

Problem D. Game

我们把棋子看作点,若两棋子的距离不超过L则在两点间连边。结论是很简单的:求这个一般图的最大匹配,如果不存在完美匹配(即有的点没有被匹配上),则先手必胜,否则后手必胜。下面说原因:

如果图中不存在完全匹配,则先手方可以先拿走任意一个不在最大匹配中的点u,则后手方不管怎么拿一定会拿到在最大匹配中的点v。(不然的话我们就可以把u-v这条边加进去得到更大的匹配,与前提矛盾)然后,每次先手方只要拿与后手方上次拿的那个点匹配的点即可。因为我们知道当得到最大匹配以后,图中是不可能存在交错增广路的,所以后手方每次都不可能选出不在匹配中的点(不然就是找到一条新的交错增广路了),这样一直进行下去,最后无路可走的一定也是后手方。

反之,若图中有完美匹配,则先手第一手无论如何都会选择在匹配中的点,然后后手就掌握主动了,像前面说的一样一直沿着这个最大匹配走下去,最终先手必败。

Problem G. Islands

这题我觉得我的做法可能有点复杂了。首先的观察是,因为不允许有多余的边,所以最后补出来的结果必定每个点都有一入一出,所以如果某个点的入度或出度大于1的话,直接无解。然后我们可以发现,如果一开始没有任何边的话,实际上这就是一个错排问题,也就是求一个1..N的排列使得每个数都不在它对应的位置上。下面先来说错排问题的递推解法(关于错排还能用容斥原理得到一个漂亮的公式,此处略):

设n个数的错排方案数是f[n],考虑最左边一个位置A,设它指向B,则有两种情况:
(1)B指回A,这时还剩n-2个数,所以问题变成了N-2个数的错排
(2)B指向A以外的数,这时我们会发现得到了一个N-1个数的错排(因为A已经确定指向B,本来是限制B不能指向自身,现在变成了限制B不能指向A,其实是一样的)

因为A一开始可以有n-1种B的选择,所以就有 f[n] = (n-1) * (f[n-1] + f[n-2])

现在的复杂之处在于这个排列里某些位置的值已经确定了(就是那些已经存在的边),除掉这种边以后,剩下的位置就分为了两类,一类是没有任何限制的,一类是不能指向它自身的。比如有五个点,已经有(2->3),(3->4)两条边,则4这个点就是没有任何限制的(它可以随便指向1或2或5),而1,5两点不能指向自身。类比错排问题的递推,我们用f[n][m]表示n个被限制不得指向自身,m个无限制的方案数,仍考虑第一个位置A,则有如下几种情况:

(1) A指向了一个有限制的B,共有(n-1)个这样的B,则有两种情况:
1a. B指回A,问题变成n-2个有限制,m个无限制
1b. B指向其他数,问题变成n-1个有限制,m个无限制(B的限制是不能指回A,类似上面错排第二种情况的讨论)

(2)A指向了一个无限制的B,共有m个这样的B,同样有两种情况:
2a. B指回A,问题变成n-1个有限制,m-1个无限制
2b. B指向其他数,变成n个有限制,m-1个无限制(这时B从无限制变成了有限制)

综上得到递推方程 f[n][m] = (n-1) * (f[n-2][m] + f[n-1][m]) + m * (f[n-1][m-1] + f[n][m-1])

边界条件是f[0][0] = 1

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

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。当然对于这道题来说,是只要敢写就可以过的,就看比赛中哪队能匀出时间来试一下了。