注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

WC2012的题目及故事  

2012-02-18 18:35:49|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我把题目的下载贴出来:
还有提交答案的数据:
http://builtinclz.abcz8.com/art/2012/catan.zip
如果你等不及下载,可以看简述:

1.mst
给一个无向图,你要修改一些边的权(权都是整数),使得它的最小生成树(MST)唯一。
每给一个边权+1或-1的代价分别是A和B。
2.memory
给平面上一堆不相交的线段,每次把一个线段横向或者纵向平移出来(沿着x或y的正或负方向一直平移到无穷远),要求不能有其他线段挡着。给一个非法的移动序列(包括移动的线段和方向),问它错在了哪一步。之后给一个正确的方案。
3.catan
类似卡坦岛的游戏,问最少用多少步能够获得10个点。

说一下memory大致算法:从左往右扫描,记录每个线段的两个端点往上、下走,最近碰到的线段。这样就可以得到一个有向无环图。计算拓扑序,这就是方案。对于一个给定的方案,把它的四个方向分开考虑。之后把时间倒流,想象成每次插入一条线段;利用拓扑序把问题转化成区间覆盖+区间最大值查询问题。
catan的算法?没有算法,你可以手玩,或者写暴搜(要强剪枝)。
mst的算法?听我仔细说。。。

mst这题是今年冬令营最让人囧的题。应twb等人的邀请,我把这题背后的“心路历程”贴到博客上。
mst这题的创意来自twb。题目的原型是:
每个边的权可加,可减,费用都是1,要求给定的一个mst成为唯一的mst。
这个是可以做的,方法是:考察一个非树边,找出它对应的树上路径上所有和它权相同的边,那么这两个边之中要么一个+1,要么一个-1,这样问题就变成最小闭合子图,可以用最小割来解了。
当然,在这个题中,可以放宽修改的费用,变成:
每个边的权可加,可减,费用分别给定,要求给定的一个mst成为唯一的mst。

不过,这个问题有点经典,于是,要进行创新:
每个边的权可加,可减,费用为1,要求mst唯一。
这个创新可是破天荒的,因为不指定mst是哪个了。不过,有一个重要的猜想:任选一个mst,得到的答案都是一样的。在这个猜想的指引下,问题依然可做。
为了让问题更难,题目变成:
每个边的权可加,可减,费用分别指定,要求mst唯一。
这是考试前一天上午的时候题目的样子。
但是,悲剧的是,我在上午听课的时候发现,这个东西,是有反例的!
  -----
 /     \
---b---d
     /
  c----
看这四个点的完全图,图中标红的a-b、a-c、b-c的边的权是1,修改代价是10000000000。其他的边的边权是2,修改代价是1。
很明显,我们应该把边权为2的边的边权降低到0,而不是去修改原来边权为1的边!
于是,题目“回退”成了这个样子:
每个边的权可加,可减,单位费用分别是A和B,要求mst唯一。
似乎一切都应该和谐了。不过,为了防止再次有反例,我们要求一份严格的证明。
这是一份证明的清单(由twb列出):
定理1:我们一定可以找的一个树,把它变成唯一的mst的代价就是问题的答案。这个树被称作“目标树”。
定理2:对于给定的目标树,我们只对树上的边进行减权操作,对树外的边进行加权操作。
定理3:任何减权操作至多减1的权值,任何加权的操作至多加1的权值。
定理4:目标树在原图上是一个mst。
定理6:任何原图上的一个mst都可以是目标树。
把这个清单列出,发现定理1是显然的,定理2是必然的,但剩下的定理证明就费劲了。
我们发现,证明最纠结的地方在于,修改之间的边和修改之后的边在逻辑上没有必然的联系。为了突破这个障碍,我们提出了一个“顺次”引理:
对权值a<b和x>y,把a修改到x、b修改到y的代价大于把a修改到y、b修改到x。这个引理是显然的。
为了让“顺次引理”作用到图上,我们提出了一个“原始置换边引理”:
对于一个mst唯一的图,我们把一个非树边和它在树上对应的路径上的一个边的权值交换,图的mst仍然唯一。
这个引理非常强大,几乎可以证明所有定理。但是,它,是错的!
反例?你自己画画就知道了。

“原始置换边引理”的失败让我们很失望。证明几乎陷入绝境。还是hwd给力,他给我们的证明以新的武器:
置换边引理:
p-q是非目标树上的一个边,u-v是p-q在树上对应的路径上的一个边。那么“顺次引理”蕴含:
p-q在原图上的权值不小于u-v在原图上的权值。
这是为什么?我们假设u-v、p-q在原图、修改之后的图上的代价分别是a、x、b、y,那么,把u-v和p-q分别修改成max(a,y),min(b,x)的效果会更好。
有了置换边引理,定理4瞬间得证。为了证明定理3,还要进行进一步的考察:
如果一条边增加了2的权值,那么为什么不能增加1呢?
如果一条边减少了2的权值,那么为什么不能减少1呢?
通过细致的分类讨论,定理3是能够被严格证明的。
有了强大的置换边引理,和定理1234,我们通过证明还可以得到定理5:
考察kruskal算法运行过程,把边权相同的边的插入视作一个阶段,那么在原图和修改后的图中,每个阶段的图的连通性原图不比修改后的图强的。
有了这个定理,我们有了算法的大致框架。
运行kruskal,把边权相同的边组成的子图分别提取出来,在这个子图上找桥,所有的桥的边权不用改变。之后对每个双连通(边)分块进行计算,相加答案即可。
问题是,每个联通块内部怎么处理呢?
我们发现,对一个边+1实际上是“删除”这条边,因为这条边不可能出现在目标树上了。
而-1实际上是把一条边选中到目标树上,也就是是把它相连的两个点缩成一个点!
于是,问题转化为:给一个图,你可能删边或者缩点,要求把它变成一个树。

我们还没法证明定理6。准确地说,我们不可能证明定理6,因为,它是错的。
zej快速敲了几百行代码,随机出了一个反例。
与此同时,我也用人脑构造了一个”壮观“的反例:
    +------+
    |一万个点的树
    +------+
           
 +--+======+--+
 |一百==一万==|一百
 |个点|==条边==|个点
 |的树|======|的树
 +--+======+--+
如果你选择了红色的生成树,那么你至少要修改10000个边。实际上,正确答案应该是只用修改200条边即可。
这时候,天已经快黑了,我们唯一的算法也没了。大家陷入绝望。
怎么办?没办法,对每个双连通块,暴搜是唯一解法。当然,记忆化可以大大加速搜索。
于是,在twb的倡议下,这题变成了“半传统”题,考试时下发数据。这样,我们就可以正大光明地构造每个双连通块都很小的测试数据了。
注意到,定理的证明对费用的唯一约束是”顺次引理”成立。这样,我们可以把题目包装成:
把权值a修改到权值b的费用是abs(a*a-b*b)。
这样,想完成问题的转化又难了一步,但是,我们不想那么邪恶。
于是,这题就成为了你看到的样子。
  评论这张
 
阅读(2352)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017