Tag Archives: SRM

一切1000pt都是纸老虎之SRM435

前言:

这里的1000pt是指Topcoder的算法类比赛中难度最大占分最高的那一道题,SRM是Single Round Match的缩写,是TC里最常见的一类算法比赛。1000pt的难度如果从ACM比赛的角度来看应算作中等偏难,但由于SRM的比赛时间紧迫(75分钟3道题)再加上不是实时返回结果,想做对的难度还是不小的(至少对我来说是这样)。之前的SRM比赛里我只注重成绩,往往来不及在比赛中做1000pt的题,结束以后也往往就不管不顾了,现在我深刻认识到自己的错误,于是打算对比较经典的1000pt难题进行一系列的分析。为了保证时效性,我尽量在每场比赛结束后官方的题解发布前写出题解,敬请关注,嘿嘿。

正文:

今天要说的是SRM 435的1000pt题目(原题见这里),题目大意是,某公司计划重组管理结构,使所有人员形成一个“森林”状结构,即若干树的集合,每个人只属于一棵树,也就是每个人至多有一个上司,要求树的个数尽可能少。这个公司在之前曾有过一些暂时管理关系,比如A曾经暂时管理过B,B可能也暂时管理过A。如果A暂时管理过B,那么A就认为他比B优秀,而且这种优越感是可传递的,即如果A管理过B,B管理过C,则A也认为他比C优秀。如果A认为自己B优秀,B也认为自己比A优秀,就说两个人有“互斥优越感”。现在要求重组后得到的森林状结构满足:

1. 任何人的下属应该是他曾经管理过的人。

2. 不应有任何人认为他比自己的直接上司优秀。

3. 有“互斥优越感”的人不应当有同一个上司。

分析:

首先,如果A曾经管理B,我们就连有向边(A,B),那么“互斥优越感”这个东西很容易让人想到强连通分量(SCC),一个SCC内部的所有人都是互斥的。我们首先考虑没有SCC的情况,这时候图是一个有向无环图(DAG),类比DAG上的最小路径覆盖问题,这题我们求的是“最小树覆盖”。如果仍套用拆点的思路,即:把每个点x拆成左右两个点x和x’,原来的边(x,y)变成新边(x,y’)得到二分图。我们会发现唯一的不同之处是,允许左边的点匹配多个右边的点,而这个只需把匹配扩展到最大流问题即可求解。

当然,无SCC的情况是trivial的,实际上我们无需求助于流直接数一下入度为0的点就可以了。但加上SCC以后问题就变得略有复杂。由条件(2),可知同一SCC内的点不可能互为上司下属关系,即若原图中有边(x,y)且x,y属于同一SCC,我们直接把这边忽略,不把它加到流网络里;由条件(3),可知同一SCC内的点不能有同一上司,即在新二分图里同一SCC的多个点不能“匹配”到左侧的同一个点上,这一限制条件不能用简单的二分图表示,我们可以再新加一列结点(三分图?),每个结点表示一个SCC,让原来二分图的边通过这个中转点卡一下,再分发出去,这样就可以表示出条件(3)的限制。具体建图过程如下:

1. 若x管理y,则连边(x,y),得到一个有向图G。对此图求强连通分量。

2. 构建网络G2:

2a. 把G中每个点x拆为两个点x和x’,再把G的每个强连通分量当作一个点,同时新加源S和汇T

2b. 对于G中的边(x,y),若x,y不属于同一SCC,则在G2中加边(x, scc[y]) (如果此边不存在的话),容量为1,再加边(scc[y], y’),容量为1。这里scc[y]表示y所属的scc。

2c. 从S到每个左侧点x加边,容量为INF

2d. 从每个右侧点x’到T加边,容量为1

3. 求G2的最大流F,则n-F即为所求

失之毫厘

前两天的TC SRM 434,前两道题的思路都很简单,结果我最后全挂得了零分。吃零蛋并不稀奇,我得过也不是一两次了,稀奇的是我死活看不出自己是怎么错的,这在以前还是很少出现过的。今天终于花了很长时间仔细检查一下我的程序,终于发现了错误的地方,没想到我这样的老油条也会犯这样的低级失误,记录一下,以防再犯:

250pt的题,中间的一步是判断一个数是不是完全平方数,这个数最多有9位。我们知道sqrt()是实数运算,用它判断总感觉不爽,为了避免精度问题,我换了一个角度,先把范围内的所有完全平方数都求出来放到一个set里,然后每次要判断的时候直接从set里找,当然这样会多一个log的计算,不过这题这样也是肯定不会超时的。但是生成这个set的时候我偷懒了,我写了一个for (i = 0 ; i < 100000 ; i++) square_set.insert(i*i); 而square_set是一个int的集合,可以发现这里是有溢出了,其实溢出我当时是想到的,只是不知怎么就以为溢出以后一定会得到不合理的负数。然后就被cha了……

500pt的题,中间需要一个高精度*单精度的乘法,以及一个高精度的比较大小。我直接把乘法模版粘过去了,结果模版有个小bug,就是在*0的时候,得到的数的len的长度不是0。这样在比较大小的时候就出现了问题,因为比较大小时先比较长度,导致0有可能反而大。然后就Fail System Test了……

连续两道题都是因为一点点的错误挂了,这样低的RP还真少见啊……

ps. 从下场开始我继续从1000pt开始做了,Rating就是个浮云,练nb了才是王道,Lord Wu教导得很对。